கைகொடுத்தல் தேற்றம்

கோட்டுரு கோட்பாட்டில் கைகொடுத்தல் துணைத்தேற்றம் அல்லது கைகுலுக்கல் துணைத்தேற்றம் (handshaking lemma) என்பதன்படி, ஒவ்வொரு முடிவுறு திசையில்லா கோட்டுருவிலும் ஒற்றைப்படை எண்ணிக்கையிலான இணைப்பைக் (முனையைத் தொட்டுக்கொண்டிருக்கும் விளிம்புகளின் எண்ணிக்கை-கூடுகையெண்) கொண்டிருக்கும் முனைகளின் எண்ணிக்கை இரட்டைப்படை எண்ணாக இருக்கும்.

இக்கோட்டுருவில் இரட்டைப்படை என்ணிக்கையில் அதாவது 2, 4, 5, 6 எனும் நான்கு முனைகள் ஒற்றைப்படை கூடுகையெண் உடையனவாக உள்ளன. அனைத்து முனைகளின் கூடுகையெண்களின் கூட்டுத்தொகை = 2 + 3 + 2 + 3 + 3 + 1 = 14 ஆகும். இது விளிம்புகளின் என்ணிக்கையைப்போல் இருமடங்கு.

பேச்சு வழக்கில் கைகொடுத்தல் தேற்றப்படி, ஒரு கூட்டத்திலுள்ளவர்களில் சிலர் ஒருவருக்கொருவர் கைகொடுக்கும்போது ஒற்றைப்படை எண்ணிக்கையில் பிறநபர்களின் கைகளைத் தொட்ட நபர்களின் எண்ணிக்கையானது இரட்டைப்படை எண்ணாக இருக்கும்.

கைகொடுத்தல் துணைத்தேற்றமானது கீழ்வரும் கூடுகையெண்களின் கூட்டுத்தொகை வாய்பாட்டின் (degree sum formula) விளைவாகப் பெறப்படுகிறது:

$\sum _{v\in V}\deg v=2|E|$

இங்கு V என்பது முனைப்புள்ளிகளின் கணம் எனவும், E என்பது இணைப்புக்கோடுகளின் (விளிம்புகள்) கணம் எனவும் கொள்க. இத்தேற்றமானது கணிதவியலாளர் லியோனார்டு ஆய்லர் 1736-ல் வெளியிட்ட ”Seven Bridges of Königsberg” என்ற புகழ்பெற்ற புத்தகத்தில் இடம்பெற்றுள்ளது.

சீரான கோட்டுருக்கள்

கூடிகையெண்களின் கூட்டுத்தொகை வாய்பாட்டின்படி, n முனைகள் கொண்ட எந்தவொரு r-சீரான கோட்டுருவும் nr/2 இணைப்புக்கோடுகளை கொண்டிருக்கும். குறிப்பாக, r என்பது ஒற்றைப்படை எண் எனில், இணைப்புக்கோடுகளின் எண்ணிக்கை r -ஆல் வகுபடும்.

முடிவிலாக் கோட்டுருக்கள்

கைகொடுத்தல் துணைத்தேற்றப்படி அமையாத முடிவிலாக் கோட்டுரு

முடிவிலாக் கோட்டுருக்களுக்கு கைகொடுத்தல் துணைத்தேற்றம் பொருந்தாது. ஒற்றைப்படை கூடுகையெண்களைக் கொண்ட முனைகளின் எண்ணிக்கையை இரட்டைப்படை எண்ணாகக் கொண்டிருக்கும் முடிவிலாக் கோட்டுருக்களுக்கும்கூட, கைகொடுத்தல் துணைத்தேற்றம் பொருந்தாது.

உசாத்துணை

1. Cameron, Kathie; Edmonds, Jack (1999), "Some graphic uses of an even number of odd nodes", Annales de l'Institut Fourier, 49 (3): 815–827, doi:10.5802/aif.1694, MR 1703426.*
2. Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140. Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press. **
3. Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.***
4. Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, MR 499124.****