A pet store decides to stock tropical fish in addition to its other pets. While trying to decide how many fish tanks to purchase, the store owner remembers that some types of fish can not be kept with some other types of fish. This is because one type eats the other type. The store owner had planned to stock five of the most popular varieties of tropical fish. The store owner consults a handbook on the care of tropical fish and determines that the following fish pairs can not be kept in the same tank:

2&1, 3&1, 3&2, 4&2, 4&3, 5&2, 5&4

The store owner needs to find the smallest number of tanks to purchase because the store has limited shelf and floor space. What is the minimum number of tanks to purchase to hold fish such that all fish in the tank are compatible?

Solution:

Represent the five types of fish by 5 nodes.

Draw an edge between incompatible fish.

Pick a node and assign it a color.

Until you have assigned a color to every node,

if there is an edge between the node and a node already colored, assign it a

different color

else

assign it an already assigned color

Note that this graph is not complete because there is no edge between nodes 1 and 5

However it is connected because there is a path from every node to every other node.