Olimpiada Nacional de Irán (3ra Ronda) 2008 Problema 7

Un grafo se llama grafo auto-intersectante si es isomorfo a un grafo cuyo cada arista es un segmento y cada dos aristas se intersecan. Observe que ninguna arista contiene un vértice excepto sus dos extremos. a) Encuentre todas las $ n$ 's para las cuales el ciclo de longitud $ n$ es auto-intersectante. b) Demuestre que en un grafo auto-intersectante $ |E(G)|\leq|V(G)|$ . c) Encuentre todos los grafos auto-intersectantes.

22

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados