Suppose that a connected planar graph has six vertices, each of degree four.…
2019
Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph?
- A.
6
- B.
8
- C.
12
- D.
20
Attempted by 191 students.
Show answer & explanation
Correct answer: B
Solution:
Compute the number of edges using the handshaking lemma. The sum of degrees is 6 × 4 = 24, and this equals 2E, so E = 24/2 = 12.
Apply Euler's formula for a connected planar graph: V − E + F = 2. Here V = 6 and E = 12, so F = 2 − 6 + 12 = 8.
Therefore the planar representation divides the plane into 8 regions.
A video solution is available for this question — log in and enroll to watch it.