Secuencia de grados en los grafos

Question

Creo que estoy haciendo algo mal en el siguiente ejercicio, pero no sé qué es.

Sea la secuencia de grados de un gráfico: $\vec{d}=(d_1,d_2,\dots,d_n)$ , donde $d_1\ge d_2\ge...\ge d_n\ge 0$ , donde $d_i$ es el grado del vértice $i$ en el gráfico. Evidentemente, hay $n$ -vértices en el gráfico.

Demostrar que existe un grafo sin bucles con secuencia de grados $\vec{d}$ si y sólo si $\sum_{i=1}^n d_i$ es par y $d_1\leq\sum_{i=2}^n d_i$ .

---

Parte $(\Rightarrow)$ : En un gráfico sin bucles, $d_1\leq m$ , donde $m=\frac{1}{2}(\sum_{i=1}^nd_i)$ . Por lo tanto: $d_1\leq \sum_{i=2}^nd_i$ .

Parte $(\Leftarrow)$ : No tengo ni idea. Por ejemplo, $n=3$ Sé que $d_1\leq d_2+d_3$ . Puedo demostrar con un ejemplo que hay un gráfico sin bucles, pero no para un caso general.

Answer 1

La parte que te falta se puede demostrar por inducción en $\sum d_i$ .

El caso base $\sum d_i=0$ se realiza mediante $n$ vértices aislados.

Supongamos que $\sum d_i>0$ Así que, por lo menos $d_1\geq1$ .

Caso 1: $d_1=d_2+\ldots+d_n$ . A continuación, tome el gráfico con vértices $v_1,\ldots,v_n$ , y $d_i$ bordes de $v_1$ a $v_i$ para todos $i=2,\ldots,n$ .

Caso 2: $d_1<d_2+\ldots+d_n$ . La diferencia entre los dos lados debe ser al menos 2, ya que la suma total es par. Como $d_1\geq1$ y $d_1$ es el valor más grande, debe haber al menos dos valores no nulos después de $d_1$ . Ahora reste 1 a los dos valores más bajos no nulos y aplicar la hipótesis de inducción. En el multigrafo resultante añade una arista entre dos vértices cuyos grados se corresponden con los valores que has reducido en la frase anterior.