Gráfico mínimo de 6 conexiones en 200 vértices

Question

Encuentra el mayor número de bordes en un gráfico conectado a 6 vértices en 200 vértices.

Creo que la respuesta es 600, usando el hecho de que$\delta(G) \geq \kappa(G)$.

Pero el gráfico más pequeño con 6 vértices conectados que podría encontrar es$K_{6,194}$ (el gráfico bipartito completo con tamaño 6 y 194), que parece muy lejos de ser óptimo ...

Una sugerencia / intuición será muy útil.

Answer 1

Como JMoritz señaló:

Creo que la gráfica con adyacencias definidas como$v_i$ es adyacente a$v_j$ con$j=((−1+i+n) \ mod \ 200)+1,$$n∈\{−3,−2,−1,1,2,3\}$. (Es decir,$v_4$ está adyacente a cada uno de$v_1,v_2,v_3,v_5,v_6,v_7$ mientras que$v_1$ está adyacente a$v_{198},v_{199},v_{200},v_2,v_3,v_4$). Cada vértice tiene exactamente 6 aristas, y usted puede verificar que en realidad tiene seis conexiones (la forma más fácil es ver que hay 6 vías de separación de vértices entre cada dos vértices, luego, por parte de Menger, podemos concluir que la gráfica está conectada 6 )