Bipartite Double Cover - Other Double Covers

Other Double Covers

In general, a graph may have multiple double covers that are different from the bipartite double cover. In the following figure, the graph C is a double cover of the graph H:

1. The graph C is a covering graph of H: there is a surjective local isomorphism f from C to H, the one indicated by the colours. For example, f maps both blue nodes in C to the blue node in H. Furthermore, let X be the neighbourhood of a blue node in C and let Y be the neighbourhood of the blue node in H; then the restriction of f to X is a bijection from X to Y. In particular, the degree of each blue node is the same. The same applies to each colour.
2. The graph C is a double cover (or 2-fold cover or 2-lift) of H: the preimage of each node in H has size 2. For example, there are exactly 2 nodes in C that are mapped to the blue node in H.

However, C is not a bipartite double cover of H or any other graph; it is not a bipartite graph.

If we replace one triangle by a square in H the resulting graph has four distinct double covers. Two of them are bipartite but only one of them is the Kronecker cover.

As another example, the graph of the icosahedron is a double cover of the complete graph K₆; to obtain a covering map from the icosahedron to K₆, map each pair of opposite vertices of the icosahedron to a single vertex of K₆. However, the icosahedron is not bipartite, so it is not the bipartite double cover of K₆. Instead, it can be obtained as the orientable double cover of an embedding of K₆ on the projective plane.