Search code examples
algorithmgraph-theoryproofbipartite

Prove that a graph is bipartite

Given a graph G in which every edge connects an even degree node with an odd degree node. How can i prove that the graph is bipartite?

Thanks in advance

Solution

  • This is the Welsh-Powell graph colouring algorithm:

    1. All vertices are sorted according to the decreasing value of their degree in a list V

    2. Colours are ordered in a list C

    3. The first non-coloured vertex v in V is coloured with the first available colour in C. "Available" means a colour that has not previously used by this algorithm

    4. The remaining part of the ordered list V is traversed and the same colour is allocated to every vertex for which no adjacent vertex has the same colour

    5. Steps 3 and 4 are applied iteratively until all the vertices have been coloured

    A graph is bipartite if it is 2-colourable. This intuitive fact is proven in Cambridge Tracts in Mathematics 131.

    This is, of course, the cannon with which to shoot a mosquito. A graph is bipartite iff its vertices can be divided into two sets, such that every edge connects a vertex from set 1 to one in set 2. You already have such a division: each edge connects a vertex from the set of odd-degree vertices, to a vertex in the set of even-degree vertices.