Demostrar que $(n, n, n-1, n-1, \ldots , 4, 4, 3, 3, 2, 2, 1, 1)$ es un gráfico!

Question

Una secuencia de enteros no negativos se llama gráfico de si existe un grafo cuyo grado de secuencia es precisamente esa secuencia.

Por ejemplo, $(1, 1, 1, 1, 1, 1)$ es un gráfico, ya que es el grado de la secuencia de gráfico

y $(3, 1, 0, 0, 0)$ no es un gráfico ya que no hay gráfico con un vértice de grado 3, un vértice de grado 1, y tres vértices de grado 0.

Ahora, la pregunta es demostrar que

$$(n, n, n-1, n-1, \ldots, 4, 4, 3, 3, 2, 2, 1, 1)$$

es siempre un gráfico.

Mi intento por construir el gráfico simple y encontrar algún patrón para la construcción de una más grande. Comenzando con $n=1$, entonces trato de construcción $n=2$. Ahora, con base en el resultado de la $n=2$, entonces de nuevo me constructo para $n=3$, y así sucesivamente.

Pero, después de hacer ese proceso, no entiendo en absoluto el patrón para la construcción de grandes gráfica de la gráfica anterior. Todo parece al azar pero bien construida. Aquí está mi proceso de dibujo:

Por favor me ayude a probar esto. Gracias antes.

Answer 1

Supongamos que comenzó con un (n,n,n-1,n-1,...,1,1) gráfico, y desea agregar dos nodos a y B, a ella. Conectar con uno de cada tipo de nodo que ya existe: uno de los n nodos, uno de los n-1 nodos, etc, todo el camino a uno de 1 nodo. También se conectan a a B, pero B para conectar nada más.

Ahora vamos a pensar acerca de lo que acaba de suceder.

• A tiene n+1 aristas (n de las conexiones a la gráfica original, más uno, a partir de ella la relación con B).
• B tiene 1 borde
• la mitad de los nodos (uno de cada tipo) en el gráfico original tiene su edgecount golpeado hasta por 1, por conectarse a la A.

Así que ahora hay dos de 2 nodos, dos de 3 nodos, ..., dos de n nodos de la gráfica original, además de B y 1-nodo que se mantuvo sin cambios como dos de 1 nodos, además de Una y la n-nodo que he topado como dos de n+1 nodos. Por lo tanto un gráfico de una talla más grande!

Answer 2

Sí hay un procedimiento inductivo: Supongamos $(n-1, n-1, n-2, n-2, \ldots, 2, 2, 1, 1)$ es la de las gráficas, y dejar que el gráfico tiene vértices etiquetados $v_{n-1}, w_{n-1}, v_{n-2}, w_{n-2}, \ldots, v_2, w_2, v_1, w_1$, donde los subíndices igual grado de vértice. anexar dos nuevos verteces $v_0, w_0$. Ahora hay una manera fácil de agregar bordes a fin de que el grado de los cambios de la lista de$(n-1, n-1, \ldots, 1, 1, 0, 0)$$(n, n, \ldots, 2, 2, 1, 1)$. Cada nuevo borde debe aumentar exactamente dos de los grados. Nota, no es necesario para mostrar exactamente lo que el nuevo gráfico, solamente que existe. Este puede ser el lugar donde su inducción consiguió empantanado(?)

Espero que esta ayuda!