BICYCLES - Editorial

Bipartite cubic graph is sometimes also refered as bicubic graph.

#3-colorability of bicubic graph

A bicubic cubic graph can always be partitioned into two parts with equal vertices on both sides. Let us say that graph has n vertices on both the sides.

Claim: Bicubic graph is 3 colorable.
Proof: The proof is constructive. We will show a way to color the edges of the graph by 3 colors such that no two edges adjacent to a vertex will have same color.

We first find a perfect matching in the graph. By using hall’s theorem, we can show that any k regular bipartite graph will always have a perfect matching. The idea is for each subset of the vertices on the left sides, the number of neighbours of that subset in right side will be never less than cardanility of the subset.

We color these edges in perfect matching by one of the colors, say red.

Now, we remove the edges of the matching. The degree of each vertex in the remaining bipartite graph will be equal to 2. A graph with all vertices having degree 2 is a collection of disjoint cycles. Due to bipartiteness condition, these cycles will be having even lengths. Now, we pick each cycle and color its edges by colors green and black alternately. Note that due to cycle length being even, the no two adjacent edges in the cycle will have same color.

Thus we proved that bicubic graph is 3 colorable.

Final solution.

Now, we select each pair colors out of the three colors (say red, green). We only consider the edges with these two colors only. Again, this graph will have degree of each vertex 2, so it will be a collection of disjoint cycles. We find these cycles by dfs.

After this procedure, we can see that each colored vertex will be part of exactly two cycles.

Implementing the solution

Finding a perfect matching in a bipartite graph can be done using Kuhn’s matching algorithm. Time complexity of Kuhn’s algorithm is usually \mathcal{O}(n \cdot m), where n number of vertices and m number of edges. There is a faster implementation of algorithm where we stop as soon as we don’t find any augmenting path/chain. The number of phases in which we find the chain are usually small. So, this approach will be reasonably fast.