I see you have some graph paper... You must be plotting something.
Probability
Level
4
Let G be a planar graph with V vertices such that each vertex has degree exactly 5. What is the least possible value of V?
The answer is 12.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The total degree of G is 5V since each vertex has a degree of 5. Each edge contributes two vertices, so we know 2E=5V.
For any planar graph, E ≤ 3 V − 6 . Plugging in what we have for E, we can simplify the inequality to become V ≥ 1 2 .
Now, our task is to figure out if there is a graph with 12 vertices and with each vertex degree 5. Although it's painful, there is indeed a graph (vertex-edge skeleton of an icosahedron).
Therefore, our answer is 1 2 .