Prueba gráfica regular

Question

Demuestre que si $G$ es un grafo conexo que no es regular, entonces $G$ contiene vértices adyacentes $u$ y $v$ tal que deg $u$ no es igual a deg $v$ .

Answer 1

Pista: Encuentra dos vértices $x$ y $y$ tal que $\deg x\ne\deg y$ . Desde $G$ está conectado, hay un camino desde $x$ a $y$ . ¿Y ahora qué?

Answer 2

$G$ es conexo, por lo que existe un camino entre dos vértices cualesquiera $a,b$ supongamos que el camino tiene n vértices $a_1,a_2...a_{n-1},b$ . Si todos los vértices adyacentes tuvieran el mismo grado $d(a_1)=d(a_2)$ y $d_(a_2)=d(a_3)\dots$