Mostrando que hay un nodo en el gráfico con una y solo una arista

Question

Mostrando que hay un nodo en el gráfico con una y solo una arista

Matemáticas
Teoría de grafos
combinatoria
principio del casillero

ManzanaDeMiOjo

Tenemos un grafo simple no dirigido con $n$ vértices donde para cada par de vértices $v_1,v_2$ , si $d(v_1)=d(v_2)$ entonces el conjunto de vecinos de $v_1$ es disjunto del conjunto de vecinos de $v_2$ . Suponiendo que el gráfico contiene al menos una arista, demuestre que hay un vértice de grado exactamente $1$ en el gráfico.

Por ejemplo, el siguiente gráfico tiene vértices de grado exactamente $1$ :

Si bien este problema se refiere a un gráfico, siento que hay una manera de aplicar la teoría del casillero para probarlo. es posible?

Sayan Dutta

Coloqué algunas ediciones con términos más técnicos para aclarar la pregunta. Comprueba si esto es realmente lo que quisiste decir.

VTand

¿No sería esto falso si el gráfico consta de

n

$n$ vértices aislados?

Sayan Dutta

@VTy eso es cierto. Pero, supongo, el OP está hablando solo de gráficos conectados. ¿Puedes encontrar un contraejemplo en gráficas conectadas?

ManzanaDeMiOjo

@VTand pero hay al menos un borde en el gráfico

ManzanaDeMiOjo

@SayanDutta aprecio las ediciones, gracias

templatetypedef

FYI un gráfico con esta propiedad se llama altamente irregular .

Respuestas (1)

Mostrando que hay un nodo en el gráfico con una y solo una arista

Coloqué algunas ediciones con términos más técnicos para aclarar la pregunta. Comprueba si esto es realmente lo que quisiste decir.
¿No sería esto falso si el gráfico consta de $n$ vértices aislados?
@VTy eso es cierto. Pero, supongo, el OP está hablando solo de gráficos conectados. ¿Puedes encontrar un contraejemplo en gráficas conectadas?
FYI un gráfico con esta propiedad se llama altamente irregular .

kabenyuk · Answer 1

Dejar $v$ sea el vértice de mayor grado y sea $\operatorname{deg}(v)=k>0$ . Dejar $N(v)$ ser vecinos del vértice $v$ . Entonces los grados de todos los vértices de $N(v)$ son distintos por pares, y si no hay vértices de grado 1 entre ellos, entonces debe haber un vértice de grado $k+1$ o más. Esto contradice la elección del vértice. $v$ .

Mostrando que hay un nodo en el gráfico con una y solo una arista

ManzanaDeMiOjo

Sayan Dutta

VTand

Sayan Dutta

ManzanaDeMiOjo

ManzanaDeMiOjo

templatetypedef

Respuestas (1)

kabenyuk

ManzanaDeMiOjo

kabenyuk

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

Número mínimo de particiones de un conjunto dada lista de números que no pueden aparecer en la misma partición

Dados 5 enteros, muestra que puedes encontrar dos cuya suma o diferencia sea divisible por 6.

Existencia de un subconjunto tal que el producto de sus elementos es un cuadrado perfecto

Una pregunta sobre la expectativa del número cromático

Mover fichas en un tablero de ajedrez

Dibuja 7 líneas en el plano de manera arbitraria. Demuestre que para cualquier configuración de este tipo, 2 de esas 7 líneas forman un ángulo menor que 26◦

(Aclaración) Un gráfico con un número par de vértices tiene dos vértices con un número par de vecinos comunes

Prueba del principio del casillero por contradicción

Una pregunta sobre un gráfico conexo con kkk