- CEMC Home
- About Us
- Contests
- Courseware
- CEMC Digital
- CEMC in Person
- Books
- Master of Mathematics
for Teachers - Educator Development
- Make a Difference
- Frequently Asked
Questions
In the graph below, vertices A,B,C,D,E,F and G represent living kidney donors and vertices 1,2,3,4,5,6,7, and 8 represent patients in need of a kidney. The edges connecting pairs of vertices represent the compatible matches between donors and patients. What is the maximum number of patients that can be matched with a compatible donor? |
Note: A patient can only receive one kidney and a live donor only has one kidney to donate.
The problem asks us to use the given graph to match as many patients as possible with compatible donors. A patient and donor must be compatible and a donor can only receive one kidney and a donor only has one kidney to donate. |
Using the graph, we can represent matching patients with compatible donors by colouring edges. We cannot colour two edges that connect to the same vertex and we cannot create a new edge. We must colour as many edges as possible in the graph.
After some careful colouring, we should come to the realization that we can colour at most 6 edges. We may have tried multiple colourings, but we are always stuck at 6.
Here is one way to colour 6 edges of the graph.
How can we be sure that there is no 7 or 8 edge colouring?