Lema de l'encaixada de mans

En aquest graf, un nombre parell de vèrtexs (els quatre enumerats amb 2, 4, 5 i 6) tenen graus senars. La suma dels graus dels vèrtexs és 2 + 3 + 2 + 3 + 3 + 1 = 14, el doble del nombre d'arestes.

En teoria de grafs, el lema de l'encaixada de mans afirma que cada graf no dirigit té un nombre parell de vèrtexs de grau senar (el grau d'un vèrtex és el nombre d'arestes que el toquen). El nom prové d'una versió més col·loquial del lema: si algunes de les persones d'un encontre s'encaixen la mà, un nombre parell de persones l'haurà encaixat amb un nombre senar d'altres.

El lema de l'encaixada de mans és una conseqüència de la fórmula de la suma de graus,

∑ v ∈ V deg ⁡ ( v ) = 2 | E | {\displaystyle \sum _{v\in V}\deg(v)=2|E|}

per un graf amb un conjunt de vèrtexs V i un conjunt d'arestes E. Ambdós resultats els demostrà Leonhard Euler en el cèlebre problema dels set ponts de Königsberg, que inicià l'estudi de la teoria de grafs.

Els vèrtexs de grau senar d'un graf sovint s'anomenen nodes senars o vèrtexs senars; amb aquesta terminologia, el lema de l'encaixada de mans es pot formular com que cada graf té un nombre parell de vèrtexs senars.

Bibliografia

  • Cameron, Kathie; Edmonds, Jack «Some graphic uses of an even number of odd nodes». Annales de l'Institut Fourier, 49, 3, 1999, pàg. 815–827. DOI: 10.5802/aif.1694.
  • Euler, L. «Solutio problematis ad geometriam situs pertinentis». A: Commentarii Academiae Scientiarum Imperialis Petropolitanae (en llatí). 8, 1736, p. 128–140 [Consulta: 30 abril 2015].  Reimpressió i traducció: Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin J. Graph Theory 1736-1936. Oxford University Press. ISBN 978-0-19-853916-2. 
  • Papadimitriou, Christos H «On the complexity of the parity argument and other inefficient proofs of existence». Journal of Computer and System Sciences, 48, 3, 1994, pàg. 498–532. DOI: 10.1016/S0022-0000(05)80063-7..
  • Thomason, A. G.. Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). 3, 1978, p. 259–268. DOI 10.1016/S0167-5060(08)70511-9. «Hamiltonian cycles and uniquely edge colourable graphs» .