Looking at the code for the colors method in friends.c,
we can see that it is exploring a tree in a depth first manner.
The root of the tree corresponds to node 1 being given color 1.
A step down the tree is done by calling colors with the next
position (p+1) with the color i. This call is in a for loop that
runs i from 1 to maxcolor-1 that are also less than or equal to P+1
(you can see this for loop as walking the siblings of the tree whose
root is p). We only continue the exploration of a branch of the tree
if `possible' is true. This is looking at all the vertices that
came earlier and making sure that if they are connected to p+1,
then they don't have the color i (if they are connected and have
the color i, then possible=0 is executed setting the flag that
prevents the recursive call from happening).
When p == n (i.e., we have hit the last city), then the tree has been
expanded to maximum depth down this branch. We then go through the
color assignments and set mc to the maximum color value used. If
this value is less than maxcolor, then we have found a `better' answer
and maxcolor is updated. You can think of the index p as a pointer
to the top of a stack of colors (kept in the array col) that mirrors
the depth first traversal of the space of possible color assignments.