Hoy he visto este problema:
Encontrar el más pequeño de $n\ge 5$ tal de que no existe un simple gráfico en $n$ vértices tal que dos vértices adyacentes no tienen en común los vecinos, y cualquiera de los dos no adyacentes vértices tienen exactamente $2$ común de los vecinos.
Yo derivados de la identidad de $\sum_{i=1}^{n} \dbinom{d_{v_i}+1}{2}=\dbinom{n}{2}$ y el uso de este, he podido demostrar que $n\ge 9$, pero no podía ir más allá. Alguna Idea?
Empezar con un vértice arbitrario $z$. Deje $D$ el conjunto de sus vecinos y deje $N$ el conjunto de vértices distintos de $z$ que se encuentra junto a algunos de vértice en $D$. Deje $d$ ser el tamaño de $D$: este es el grado de $z$. No hay dos vértices de $D$ son adyacentes el uno al otro (ya que cada par tiene un común vecino, es decir,$z$).
Así que cada pareja debe tener también una común vecino otro de $z$, y que es común el vecino está en $N$. Obtenemos un bien definidos, inyectiva asignación de "pares de vértices en $D$" en "vértices en $N$". La razón por la que este mapa es inyectiva, es que diferentes parejas deben encontrar diferentes común de los vecinos en $N$: si dos pares compartido el mismo vecino$v \in N$,, a continuación, $z$ e $v$ tendría más de 2 amigos en común.
De hecho, el mismo argumento muestra que nuestra asignación es también en: cada vértice de $N$ es tan común vecino para un cierto par de vértices en $D$, ya que de los dos debe tener amigos en común con $z$. Por lo tanto, nuestra asignación es uno-a-uno y a, y $N = \binom{d}{2}$.
Ahora una observación clave es que el $\{z\} \cup D \cup N$ son todos los vértices del grafo, desde cualquier vértice fuera de esta unión no puede tener ningún mutuo vecino con $z$ lo cual está prohibido. Por lo que el número de vértices del grafo es $n=1+d+\binom{d}{2}$, y desde $z$ fue completamente arbitraria nos encontramos con que el grafo es regular: todos los vértices deben tener el mismo grado de $d$, lo que hace $n=1+d+\binom{d}{2}$ cierto.
Nos deja etiquetar los elementos de $D$ con los enteros $\{1,2,\ldots,d\}$. Los elementos de $N$ son naturalmente etiquetados por (desordenada) pares de $\{i, j\}$ con $1 \leq i \neq j \leq d$, y el vértice (correspondiente) $\{i,j\}$ está conectado a dos vértices de $D$, es decir, $i$ e $j$. Desde $\{i,j\}$ tiene el grado $d$, debe tener $d-2$ adicional de los vecinos en $N$ sí.
Considere dos vértices de $N$, decir $\{i,j\}$ e $\{i,k\}$, que comparten un amigo $i \in D$. Tener un amigo en común, implica que ellos mismos no deben ser adyacentes. Puesto que para cada par de número de $\{i,j\}$ podemos encontrar $2d-4$ otros pares que se cruzan de esta manera, nos encontramos con que cada una de las $\{i,j\} \in N$ ha $2d-4$ no-vecinos en $N$.
De ello se desprende que $N$ contiene al menos $1+(d-2)+(2d-4)$ vértices, y desde $N=\binom{d}{2}$ debemos tener $3d-5 \leq \binom{d}{2}$. Esta falla por $d=3,4$ (en el caso de $d=2$ corresponde obviamente al caso en que el conjunto de la gráfica es sólo un 4-ciclo, que satisface todos los requisitos, excepto que se ha $n<5$ vértices). Que hace el trabajo para $d=5$, por lo que este es nuestro candidato para el más pequeño de respuesta: 5 gráfico regular con 16 vértices. Asumimos $d=5$ a partir de ahora.
Así que considere de nuevo arbitraria miembro de la $\{i,j\}$ de % de$N$, con $i,j$ ahora en el rango de $\{1,\ldots,5\}$. Dispone de 6 de no-amigos en $N$ (todos los pares que incluyen cualquiera de las $i$ o $j$) y 3 amigos, que por ende debe ser exactamente todos los pares de $\{k,l\}$ que son distintos de $\{i,j\}$. Usted puede reconocer esto como una de las descripciones de la Petersen gráfico: hemos llegado a la conclusión de que el grafo inducido por $N$ es Petersen.
De hecho, ahora tenemos una descripción completa de todo el gráfico: consta de 3 conjuntos de vértices, $\{z\}$, $D=\{1,\ldots,5\}$ y $N=$ el conjunto de pares de elementos de $D$. Cada vértice $\{i,j\}$ en $N$ está conectado a $i$ e a $j$ en $D$ así como a los vértices $\{k,l\}$ en $N$ que son distintos de él.
Es fácil comprobar que esta construcción cumple con todos los requisitos del problema, y como se señaló en los comentarios, no es otro que el de Clebsch gráfico.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
