¿Cómo demostrar que al menos dos vértices tienen el mismo grado en cualquier gráfico?

Question

Quiero demostrar que al menos dos vértices tienen el mismo grado en cualquier grafo (con 2 o más vértices). Tengo en mente algunos gráficos que demuestran que esta afirmación es correcta, pero ¿cómo podría demostrarlo (o refutarlo) para TODOS los gráficos?

Answer 1

Digamos que el grafo es simple, sin bucles y que todos los vértices tienen diferente grado $d_1,d_2,...d_n$ entonces $$\{d_1,d_2,...d_n\} = \{0,1,2...,n-1\}$$

Por tanto, hay un vértice de grado $n-1$ y un vértice de grado $0$ . Una contradicción.

Answer 2

Supongo que estamos hablando de gráficos finitos. Estoy bastante seguro de que tu afirmación es falsa para grafos infinitos.

Supongamos que un gráfico finito $G$ tiene $n$ vértices. Entonces cada vértice tiene un grado entre $n-1$ y $0$ . Pero si algún vértice tiene grado $0$ entonces ningún vértice puede tener grado $n-1$ por lo que no es posible que los grados de los vértices del grafo incluyan tanto $0$ y $n-1$ . Así, el $n$ Los vértices del gráfico sólo pueden tener $n-1$ diferentes grados, por lo que por el principio de encasillamiento al menos dos vértices deben tener el mismo grado.

Answer 3

EDIT: Los grafos se definen normalmente como finitos. Los grafos infinitos son una generalización. Yo no sabía esto en el momento de la publicación. Sin embargo, dejaré esta respuesta por si alguien la encuentra útil.

He aquí un contraejemplo.

Dejemos que $G$ sea un grafo sobre los enteros positivos donde hay una arista desde $x$ à $y$ si $x < y \le 2x$ . Obsérvese que ignoraremos la dirección de las aristas. Así que $2$ por ejemplo, es vecina de $1$ , $3$ y $4$ .

Dejemos que $j$ y $k$ sean enteros positivos distintos. Sin pérdida de generalidad, supongamos que $j < k$ . Tenga en cuenta que $deg(j) = j + \lfloor j/2 \rfloor$ y $deg(k) = k + \lfloor k/2 \rfloor$ . Tenemos que

$$j < k$$ $$\lfloor j/2 \rfloor \le \lfloor k/2 \rfloor$$ $$j + \lfloor j/2 \rfloor < k + \lfloor k/2 \rfloor$$ $$deg(j) < deg(k)$$ $$deg(j) \neq deg(k)$$

Por lo tanto, no habrá dos vértices diferentes que tengan el mismo grado. $\square$