Problem 29 · 2011 Math Kangaroo
Stretch
Counting & Probability
careful-countingcasework
In how many ways can one choose four edges of a cube so that no two of these edges share a common corner?
Show answer
Answer: C — 9
Show hints
Hint 1 of 2
Four edges with no shared corner must use all eight vertices exactly once — a perfect matching of the cube.
Still stuck? Show hint 2 →
Hint 2 of 2
Count the perfect matchings of the cube's edge graph.
Show solution
Approach: count perfect matchings of the cube
- Four edges meeting no common corner cover all 8 vertices once each, i.e. a perfect matching.
- The three pairs of opposite faces give matchings of parallel edges (6 of them), plus three 'skew' matchings.
- Altogether the cube graph has 9 perfect matchings.
- So there are 9 ways, choice (C).
Mark:
· log in to save