Distribución de$k$ no dirigido: el gráfico regular tiene el número d de vértices más que$k^{2} + 1$

Question

He encontrado esto: Gráfico con la circunferencia de 5 y exactamente $k^2+1$ vértices

El autor sin embargo no dice cómo demostró el lema (mi título). Tratando de resolver esto de (#3) aquí:

http://cse.iitkgp.ac.in/~agupta/gráfico/Sol-H2.pdf

el último es muy perspicaz. Sin embargo, aplicando lo que creo que va a tomar yo no se, a partir de una cadena de 5 bordes con los extremos de los vértices que yo llamo la u y v. Ahora bien, si u y v están conectados tendríamos un gráfico con 5 vértices y una circunferencia de 5; un pentágono. Ahora bien, si u y v no están conectados tenemos que hay k-1 vértices que u puede ser conectado y lo mismo con v. Ahora, de cualquier manera u y v tienen que ser conectados a algo así como a crear un ciclo por lo tanto, hay k-2 bordes saliendo de cada u y v. Así que si multiplico $(k-2)(k-2)$ y añadir el número de vértices ya en la gráfica (5) se tiene la ecuación de $(k-2)^{2}+5 = k^{2}-4k+4+5= k^{2}-4k+9$.

Ahora si tenemos la 2-regular el gráfico circunferencia 5 (el pentágono) luego me conecte k=2 y obtenga $2^{2}-4(2)+9 = 5$ que es precisamente igual a $k^2 + 1 = (2)^{2}+1 = 5$. Sin embargo, esto no es mayor que la original propuesta de $k^{2} + 1$ lugar es igual. No sé lo que está pasando aquí y además no estoy seguro de cómo elaborar un "formal" prueba de ello - si estoy en el camino correcto.

Gracias por tus pensamientos,

Brian

Answer 1

Usted citar erróneamente las palabras de la declaración original. Afirma que "un gráfico con la circunferencia 5 y el grado de, al menos, $k$ tiene al menos $k^2+1$ vértices."

El "al menos" debe ser traducido como "más que o igual a"

---

Para una prueba de este lema general, considere el caso donde la gráfica tiene la circunferencia $2n+1$ y el grado al menos $k$.

Pick 1 vértice, llame a $A$. Está conectado a $k$ otros vértices. Llamar a estos vértices $A_{1}$$A_{k}$.
Estos vértices están conectados a $A$, e $k-1$ otros vértices. Llamar a estos vértices $A_{1,1}$$A_{k, k-1}$.
Seguir este procedimiento para $n$ de veces, así que hemos vértices etiquetados de la a a $A_{a_1, a_2, \ldots a_n}$ donde$1 \leq a_1 \leq k$$0 \leq a_i \leq k-1$$2\leq i \leq n$.

Reclamo: Estos vértices son distintos. Si no son distintos, entonces la circunferencia es menor que $2n+1$.

Tenemos $k^n +1$ distintos vértices etiquetados, por lo que la gráfica tiene al menos $k^n+1$ vértices.