Combinatoria
Olimpiada Nacional de Irán (3ra Ronda) (2008)
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