Olimpiada Nacional de Irán (2da ronda) 1993 Problema 4

$G$ es un grafo con $n$ vértices $A_1,A_2,\ldots,A_n,$ tal que para cada par de vértices no adyacentes $A_i$ y $A_j$ , existe otro vértice $A_k$ que es adyacente tanto a $A_i$ como a $A_j$. (a) Encuentre el número mínimo de aristas en dicho grafo. (b) Si $n = 6$ y $A_1,A_2,A_3,A_4,A_5,$ y $A_6$ forman un ciclo de longitud $6,$ encuentre el número de aristas que deben agregarse a este ciclo para que se cumpla la condición anterior.

22

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados