168 10. Matchings in Graphs
species, just in case the tortoises want to pick totems too). Drawing the
tribe-nodes on the left and the tortoise-nodes on the right makes it clear
that we get a bipartite graph (Figure 10.3). And what is it that we want
to prove? It is that this graph has a perfect matching!
654321FEDCBAFIGURE 10.3. The graph of tribes and tortoisesSo this is very similar to the problem discussed (but not solved!) in the
previous section: We want to prove that a certain bipartite graph has a
perfect matching. Theorem 10.1.1 says that for this conclusion it suffices
to know that every node has the same degree. But this is too strong a
condition; it is not at all fulfilled in our example (tribe B has only two
tortoises to choose from, while tribe D has four).
So what property of this graph should guarantee that a perfect match-
ing exists? Turning this question around: What wouldexcludea perfect
matching?
For example, it would be bad if a tribe could not find any tortoises on its
own territory. In the graph, this would correspond to a node with degree
- Now this is not a danger, since we know that tortoises occur everywhere
on the island.
It would also be bad (and this has come up already) if two tribes could
only choose one and the same tortoise. But then this tortoise would have
an area of at least 200 square miles, which is not the case. A somewhat
more subtle sort of trouble would arise if three tribes had only two tortoises
on their combined territory. But this, too, is impossible: The two species of
tortoises would cover an area of at least 300 square miles, so one of them
would have to cover more than 100. More generally, we can see that the
combined territory of anyktribes holds at leastkspecies of tortoises. In
terms of the graph, this means that for anyknodes on the left, there are