Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A simple graph has exactly edges. Three of its vertices have degree , and every other vertex has degree . There are no other vertices.
Find the number of vertices of degree and the total number of vertices. Then check that such a graph really exists by the Havel–Hakimi test, or by describing one.
The degrees add up to twice the number of edges, so the number of odd vertices is even. has edges. A simple graph on vertices with more than edges is connected.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. The degree sum. .
Step 2. Solve. , so vertices of degree , and vertices in all.
Step 3. Does it exist? Test 4, 4, 4, 3, 3, 3, 3. Remove a and subtract from the next four degrees: 3, 3, 2, 2, 3, 3, which sorts to 3, 3, 3, 3, 2, 2. Remove a : . That is the cycle , so every step works back to a real graph.
Check. .
Answer: vertices of degree , and vertices in all.
Log in to join the discussion.
Loading…