Problem 22 · 2014 Math Kangaroo
Stretch
Counting & Probability
careful-countingcasework
In the diagram Karl wants to add lines, each joining two of the marked points, so that each of the seven marked points is joined to the same number of other marked points. What is the minimum number of lines he must draw?
Show answer
Answer: D — 9
Show hints
Hint 1 of 2
Count the degree (number of lines) already at each of the seven points.
Still stuck? Show hint 2 →
Hint 2 of 2
Add the fewest lines so every point ends with the same degree.
Show solution
Approach: equalise the seven vertex degrees with the fewest added edges
- From the diagram the current degrees are 3, 2, 1, 1, 1, 1, 1 (sum 10, i.e. 5 existing lines).
- Raising every vertex to a common degree needs a minimum of 9 extra lines.
- So he must draw 9 lines.
Mark:
· log in to save