Un gráfico definido por un conjunto de enteros positivos

Question

Estoy luchando por encontrar una prueba para esta proposición de la teoría de grafos cromáticos de bundy.

Que sea $S$ un conjunto de enteros positivos, con el elemento máximo $n$ . Existe un gráfico $G$ en $n+1$ vértices tales que:

1. Para cada vértice $u\in V(G)$ tenemos que $d(u)\in S$
2. Para todos $k\in S$ existe un vértice $v\in V(G)$ tal que $d(v)=k$

Lo que intento es utilizar la inducción en la cardinalidad de $S = n$ , para $n =1$ tenemos el gráfico completo, y cuando $n=2$ , nosotros si tenemos $m_1$ , $m_2$ si $m_1$ es menor que $m_2$ podemos hacer el completo en $m_1$ vértice y luego combinar con $m_2- m_1 + 1$ vértice utilizando el producto entre grafos, pero cuando intento hacer el paso inductivo me bloqueo, pruebo a quitar $n$ y disminuir todos los elementos 1 grado si tengo 1 en $S$ es fácil simplemente añadir el vértice que van a necesitar ya que no sabemos si el segundo elemento más grande es $n - 1$ . Pero si 1 no está en $S$ No sé cómo proceder. ¿Es este el enfoque correcto? Preferiría una pista, o una sugerencia sobre otro enfoque

Answer 1

Por lo que sé, es posible modificar sus intentos para que funcionen en cada caso. Como se pide...

Consejos :

1. Hay dos formas de aplicar la inducción: borrando $n$ de $S$ y restando $1$ de todo en $S$ . Funcionan en diferentes casos.

2. Cuando $n-1 \not\in S$ , intente reemplazar $S$ con $S \cup \{n-1\}$ .

Pero para los que no quieren pistas... inducimos en $n=|S|$ . Casos básicos : es cierto cuando $n=1$ realizado por $K_2$ y cuando $n=2$ realizado por $K_3$ y $K_3$ menos un borde. Supongamos ahora $n \geq 3$ .

Caso I : $1 \in S$ y $n-1 \in S$ .

Aplicamos la inducción a $S':=\{d-1:d \in S \setminus \{n,1\}\}$ . Desde $\mathrm{max}(S')=n-2$ obtenemos un $(n-1)$ -gráfico de vértices con grado igual a $S'$ Entonces (a) añadimos un vértice aislado, y (b) añadimos un vértice y lo conectamos a cualquier otro vértice. Así se obtiene un $(n+1)$ -gráfico de vértices con grado igual a $S$ .

Caso II : $1 \in S$ y $n-1 \not\in S$ .

Aplicamos la inducción a $S':=(S \setminus \{n\}) \cup \{n-1\}$ . Desde $\mathrm{max}(S')=n-1$ , obtenemos un $n$ -gráfico de vértices con grado igual a $S'$ y añadir un borde colgante al grado $(n-1)$ vértice (teniendo en cuenta que sólo puede haber uno, de lo contrario nos contradecimos $1 \in S'$ ).

Caso III : $1 \not\in S$ .

Aplicamos la inducción a $S':=\{d-1:d \in S\}$ . Desde $\mathrm{max}(S')=n-1$ obtenemos un $n$ -gráfico de vértices con grado igual a $S'$ , entonces añadimos un vértice y lo conectamos a todos los demás vértices. De este modo se obtiene un $(n+1)$ -gráfico de vértices con grado igual a $S$ (terminamos con $2$ grado- $n$ vértices).

Y observo que en los tres casos el modificado $S$ es no vacía, por lo que tiene un elemento máximo.

Answer 2

Puedo hacer el punto 2. Todavía estoy trabajando en el 1.

Intentemos dibujar $G$ dado $S$ . El elemento máximo del elemento es $n$ . Está claro que podemos tener un vértice en un grafo con $n+1$ vértices cuyo grado es $n$ .

Los otros elementos posibles en $S$ son $1,2,...,n-1$ desde $n$ es el elemento más grande ( $S$ puede tener sólo algunos de ellos).

No hay problema en dibujar un gráfico $G$ en $n+1$ vértices cuyos grados tienen un grado entre $1,2,3,...,n-2,n-1$ y cada uno de los números $1,2,3,...,n-2,n-1$ es el grado de al menos un vértice de la siguiente manera. Etiqueta los vértices de $G$ por $v_1,v_2,...,v_n,v_{n+1}$ . Dar vértice $v_1$ grado $n$ (haciéndolo adyacente a todos los $v_2,v_3,...,v_n,v_{n+1}$ ). Entonces da el vértice $v_2$ grado $n-1$ (haciéndola adyacente a una cantidad suficiente de $v_3,...,v_n,n_{n+1}$ empezando por el vértice más a la izquierda de la lista, para dar $v_2$ grado $n-1$ ). Y así sucesivamente. Yuu terminará con dos vértices del mismo grado.

Ahora, supongamos que uno de los números $1,2,3,...,n-2,n-1$ no está contenida en $S$ . El gráfico descrito anteriormente sigue satisfaciendo el requisito, ya que todos los posibles números que podrían estar en $S$ (es decir $1,2,3,...,n-2,n-1$ ) son el grado de al menos un vértice de $G$ . Así que hemos terminado.