Teoría de grafos - grado de vértices en un grafo simple

Question

"Vamos a G ser un simple gráfico. Cualquiera de probar que existen dos vértices de G con el mismo grado o encontrar un ejemplo en el que todos los vértices tienen un grado diferente."

Así que, aquí está lo que yo pensaba. Un simple gráfico puede ser un árbol que se puede construir al aumentar en 1 el grado de cada vértice en comparación con todo lo demás. Sin embargo, no sé cómo expresarlo como un ejemplo, porque vamos a tener un gráfico que es infinito.

Alguien me puede ayudar con eso? O, ¿alguien puede poner la base para la prueba?

Cualquier ayuda es muy apreciada.

Answer 1

Sugerencia: En un gráfico simple $G=(V, E)$ a $n$ vértices, el máximo grado de un vértice es $n-1$. En particular, el conjunto de posibles grados es $A := \{0, 1, \ldots, n-1\}$, y tiene cardinalidad $n$. Ahora supongamos que cada vértice en el grafo $G$ tiene un distinto grado. Entonces podemos definir una inyección $$\phi: V \rightarrow A$$ $$v \mapsto deg(v).$$

Pero $V$ e $A$ tienen la misma cardinalidad, por lo que de inyectividad en realidad implica ___________.

Ahora tenga en cuenta que la única manera de que un vértice tiene grado $n-1$ es si es adyacente a todos los demás vértices en la gráfica. Se puede encontrar una contradicción?

Answer 2

Seguí trabajando en ello y me di cuenta de que estaba equivocado. Esta es mi prueba ahora, ¿alguien puede revisarlo?