Exercise · ZW-PLANAR-GRAPH-005 · ★★☆ Intermediate
Why is \(K_5\) not planar?
Choose one option.
Show answer
- C. It has 10 edges while \(3v-6=9\), so it violates \(e\le 3v-6\)
Explanation
\(K_5\) has \(\binom52=10\) edges, more than \(3\cdot5-6=9\), the maximum for a simple planar graph. \(K_4\) is complete and planar, and cycles do not prevent planarity.
Review the concept: Planar graph
A planar graph is a graph that can be drawn in the plane with no crossing edges; such a drawing, for \(v\) vertices and \(e\) edges, splits the plane into \(f\) faces.
\[v-e+f=2\]
More practice problems: planar graph
- ZW-PLANAR-GRAPH-001 Which of the following complete graphs is planar?
- ZW-PLANAR-GRAPH-002 A connected planar graph has v=8 vertices and e=12 edges. How many faces (counting the outer one) d…
- ZW-PLANAR-GRAPH-003 A plane drawing of a connected graph has 6 vertices and 5 faces. How many edges does it have?
- ZW-PLANAR-GRAPH-004 A simple, connected, planar graph has v=7 vertices. What is the largest possible number of edges?
- ZW-PLANAR-GRAPH-006 A tree with 10 vertices is drawn in the plane. How many faces does the drawing have?
- ZW-PLANAR-GRAPH-007 A planar graph, not necessarily connected, has 2 connected components, v=9 vertices and e=10 edges.…
- ZW-PLANAR-GRAPH-008 A connected planar graph with no triangles satisfies e≤ 2v-4. Is K_3,3 (6 vertices, 9 edges, no tri…
- ZW-PLANAR-GRAPH-009 A maximal planar graph with v=10 vertices (every face a triangle) has e=24 edges. How many faces do…