- CEMC Home
- About Us
- CEMC Digital
- CEMC in Person
- Master of Mathematics
- Educator Development
- Make a Difference
- Frequently Asked
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?