Let G be a connected planar graph with 10 vertices. If the number of edges on…
2015
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is ___________.
Attempted by 153 students.
Show answer & explanation
Correct answer: 24
Given: v = 10 vertices and each face is a triangle (has 3 edges).
Key facts and relations:
Each face has 3 edges, and each edge is counted for two faces in a planar embedding, so 3f = 2e.
Euler's formula for a connected planar graph: v - e + f = 2.
Combine the relations:
From 3f = 2e, we get f = 2e/3. Substitute into Euler: 10 - e + (2e)/3 = 2
Multiply by 3: 30 - 3e + 2e = 6
So -e = -24, hence e = 24.
Answer: The graph has 24 edges.