Pregunta de teoría de grafos extremadamente difícil

Question

La siguiente pregunta estaba en mi examen de introducción a la combinatoria y teoría de grafos. Pregunté por ahí y parece que nadie consiguió resolverla. Yo, desde luego, no lo he conseguido, incluso ahora, después de pensar en ella durante unas horas. Agradecería cualquier ayuda.

Demuéstralo: Que hay $n_0\in\mathbb{N}$ de manera que para cada $n>n_0$ hay dos grafos no isomorfos, $G_1$ y $G_2$ tal que..:

• $G_1$ y $G_2$ cada uno tiene $2n$ vértices y $n^2$ bordes
• Para cada número entero $k$ , $1\le k\le\left \lfloor{\sqrt{n}}\right \rfloor$ el número de caminos simples de longitud $k$ de $G_1$ es igual al número de caminos simples de longitud $k$ de $G_2$ .

Gracias a todos los que lo prueben.

Answer 1

Parece un problema interesante, aunque parece difícil para una pregunta de examen.

Una idea sería aprovechar el hecho de que sólo te interesan los trayectos relativamente cortos, así que asegúrate de $G_1$ y $G_2$ difieren sólo a gran escala. Por ejemplo, consideremos 6 vértices conjuntos $K_t$ (donde $t$ se elegirá más adelante), cada uno con un vértice distinguido. En $G_1$ conectan estos vértices con caminos de longitud $\sqrt{n}$ en forma de hexágono. En $G_2$ hacer lo mismo, pero en forma de dos triángulos disjuntos.

Ahora los gráficos son "localmente" iguales, es fácil demostrar que tienen el mismo número de caminos cortos. El único problema es que estos gráficos tienen muy pocas aristas. Así que en los restantes $2n-6(t+\sqrt{n})$ vértices, añade un componente con el número de aristas necesario para $G_1$ y $G_2$ . Tendrá que elegir $t$ adecuadamente para que esto funcione, pero no es difícil.

Answer 2

Acabo de darme cuenta de que no he publicado mi respuesta. Más vale tarde que nunca. Disculpas. La siguiente respuesta se basa en la visión del usuario264781.

Dejemos que $b\in\mathbb{N}$ . Sea $C_{b\left \lfloor{\sqrt{n}}\right \rfloor}$ sea un círculo con $b\left \lfloor{\sqrt{n}}\right \rfloor$ vértices. Para $1 \le k \le \left \lfloor{\sqrt{n}}\right \rfloor$ Hay $b\left \lfloor{\sqrt{n}}\right \rfloor$ caminos de longitud $k$ en $C_{b\left \lfloor{\sqrt{n}}\right \rfloor}$ .

Dejemos que $K_{2n-6b\left \lfloor{\sqrt{n}}\right \rfloor}$ sea un grafo completo con $2n-6\left \lfloor{\sqrt{n}}\right \rfloor$ vértices. Tiene $K_V = {{2n-6\left \lfloor{\sqrt{n}}\right \rfloor} \choose 2} = (n-3\left \lfloor{\sqrt{n}}\right \rfloor)(2n-6\left \lfloor{\sqrt{n}}\right \rfloor -1)$ bordes. También, $\lim\limits_{n\to\infty}\frac{K_V}{n^2-6\left \lfloor{\sqrt{n}}\right \rfloor} =2$ . Por lo tanto, $K_V > n^2-6\left \lfloor{\sqrt{n}}\right \rfloor$ para un tamaño lo suficientemente grande $n$ .

Así, para $n>N$ , dejemos que $T(n) = (V, E)$ sea un gráfico con $2n-6\left \lfloor{\sqrt{n}}\right \rfloor$ vértices y $n^2-6\left \lfloor{\sqrt{n}}\right \rfloor$ bordes, tal que:

• $E(T(n)) = E(K_{2n-6\left \lfloor{\sqrt{n}}\right \rfloor}) -A$ para algunos $A \subset E(K_{2n-6\left \lfloor{\sqrt{n}}\right \rfloor})$ , $|A|=6\left \lfloor{\sqrt{n}}\right \rfloor$
• $V(T(n))=V(K_{2n-6\left \lfloor{\sqrt{n}}\right \rfloor})$

Dejemos que $G_1$ sea la unión de los gráficos $T(n)$ , $C_{3\left \lfloor{\sqrt{n}}\right \rfloor}$ y $C_{3\left \lfloor{\sqrt{n}}\right \rfloor}$ . Sea $G_2$ sea la unión de los gráficos $T(n)$ y $C_{6\left \lfloor{\sqrt{n}}\right \rfloor}$ .

De nuestra construcción, $G_1$ y $G_2$ tienen exactamente $2n$ vértices y $n^2$ bordes. Además, no son isomorfas porque tienen diferente número de componentes de conectividad.

Dejemos que $f(G, k)$ sea el número de caminos de longitud $k$ en el gráfico $G$ Y luego, para $1 \le k \le \left \lfloor{\sqrt{n}}\right \rfloor$ : \begin{align} f(G_1, k)&=f(T(n), k) + 2f(C_{3\left \lfloor{\sqrt{n}}\right \rfloor})\\\\ &=f(T(n), k) + 6\left \lfloor{\sqrt{n}}\right \rfloor\\\\ &=f(T(n), k) + f(C_{6\left \lfloor{\sqrt{n}}\right \rfloor})\\\\ &=f(G_2, k) \end{align} $\blacksquare$