Ejercicio · ZW-GRAFO-PLANAR-005 · ★★☆ Intermedio
¿Por qué \(K_5\) no es planar?
Elige una opción.
Ver respuesta
- C. Tiene 10 aristas y \(3v-6=9\), así que viola \(e\le 3v-6\)
Explicación
\(K_5\) tiene \(\binom52=10\) aristas, más que \(3\cdot5-6=9\), el máximo para un grafo simple planar. \(K_4\) es completo y sí es planar, y los ciclos no impiden la planaridad.
Repasa el concepto: Grafo planar
Un grafo planar es un grafo que admite un dibujo en el plano sin cruces de aristas; ese dibujo, para \(v\) vértices y \(e\) aristas, divide el plano en \(f\) caras.
\[v-e+f=2\]
Más ejercicios de grafo planar
- ZW-GRAFO-PLANAR-001 ¿Cuál de los siguientes grafos completos es planar?
- ZW-GRAFO-PLANAR-002 Un grafo conexo planar tiene v=8 vértices y e=12 aristas. ¿Cuántas caras (contando la exterior) tie…
- ZW-GRAFO-PLANAR-003 Un dibujo plano de un grafo conexo tiene 6 vértices y 5 caras. ¿Cuántas aristas tiene?
- ZW-GRAFO-PLANAR-004 Un grafo simple, conexo y planar tiene v=7 vértices. ¿Cuál es el mayor número posible de aristas?
- ZW-GRAFO-PLANAR-006 Un árbol con 10 vértices se dibuja en el plano. ¿Cuántas caras tiene el dibujo?
- ZW-GRAFO-PLANAR-007 Un grafo planar, no necesariamente conexo, tiene 2 componentes conexas, v=9 vértices y e=10 aristas…
- ZW-GRAFO-PLANAR-008 Un grafo conexo planar sin triángulos cumple e≤ 2v-4. K_3,3 (6 vértices, 9 aristas, sin triángulos)…
- ZW-GRAFO-PLANAR-009 Un grafo planar maximal con v=10 vértices (todas las caras son triángulos) tiene e=24 aristas. ¿Cuá…