Each edge of a finite connected graph is colored with one of N colors in such a way that there is just one edge of each color at each point. One edge of each color but one is deleted. Show that the graph remains connected.
Solution
Induction on N. For N=2, the graph must be a cycle with edges of alternating color, so removing one edge will not disconnect it. Now assume the result is true for N.
Take a graph colored with N+1 colors such that there is just one edge of each color at each point. Remove all the edges of one color X. If the graph remains connected, then it still has an edge of each color at each point, so by induction if we remove an edge of each color but one, then it remains connected. Obviously, if we now put back all but one of the X-colored edges, then it remains connected. So suppose removing all the edges of color X disconnects the graph, giving components C1, C2, ... , Cr. By induction removing an edge of each color but one does not disconnect any of the components. Now each component must have an even number of points (because before removing the edges, if there are k points, then there are k/2 edges of any given color). Hence if we now put back the X-colored edges, then each component has an even number of X-colored edges to the other components. So if we regard the components as points, then every point of the resulting graph has even degree. But that means that every edge must be part of a cycle, so removing a single edge cannot disconnect the graph. Hence removing a single X-colored edge must leave all the components connected together and hence leave the graph connected.
Thanks to Vikram Nayak
© John Scholes
jscholes@kalva.demon.co.uk
19 January 2004
Last corrected/updated 19 Jan 04