He visto en varios parciales viejos, ejemplo Parcial Julio 2015 donde se menciona una propiedad llamada "Handshaking" que creo no se vió en el teórico. Que es? Ya no se da más?
Tengo la misma consulta
Handshaking sale del teorema de que la suma de los grados de los vertices es el doble que las aristas, y es que la cantidad de personas que saludan (“handshake”, o dar la mano en español) a una cantidad impar de personas es par. En terminos de grafos, es que la cantidad de vertices con grado impar es par. Espero que haya servido!
Se refiere al "handshaking lemma" o lema del apretón de manos, dice que la suma de los grados de cada vértice da el doble de la cantidad de aristas (equivalentemente para grafos planos, la suma de los grados de las caras o regiones da el doble de las aristas). Confunde pues no se le puso un nombre en clases a este lema, pero así se llama.