How do you check whether a graph is bipartite, and what does bipartite mean?
A graph is bipartite when its nodes can be split into two groups so that every edge joins a node in one group to a node in the other group. There are no edges inside a group.
a bipartite graph the colours
---------------------- ---------------------------
a square A red, B blue, C red, D blue
A-B, B-C, C-D, D-A
the same square with one more edge
A-B, B-C, C-D, D-A, A-C
this one is not bipartite
And how do you check it? You put one node in the first group, and then you spread out from it. Every neighbour of a node has to go in the other group. And if you ever find a node that has to be in the group it is already in, then the graph is not bipartite.
the steps what you do
--------------------------- ------------------------------
take a node with no colour give it the first colour
take a coloured node give its neighbours the other one
find a neighbour with the the graph is not bipartite
same colour
And the reason for the rule is a simple counting argument. A node has to be in the opposite group from all of its neighbours. And a neighbour of a neighbour has to be in the same group as the first node. So the colour of a node is forced by the colour of the node you started from, and if the graph has an odd cycle then you come back to the start with the other colour and there is a contradiction.
And that is the connection to the odd cycle test. A graph is bipartite if and only if it has no odd cycle.
And the complexity is O of n plus m for the time, because every node is coloured once and every edge is looked at once, and O of n for the space of the colour dictionary.
So the rule to remember is this. Two colours, and every edge must join two different colours.
The last question in this topic shows the code.