Bipartite Double Cover - Construction

Construction

The bipartite double cover of G has two vertices u_i and w_i for each vertex v_i of G. Two vertices u_i and w_j are connected by an edge in the double cover if and only if v_i and v_j are connected by an edge in G. For instance, below is an illustration of a bipartite double cover of a non-bipartite graph G. In the illustration, each vertex in the tensor product is shown using a color from the first term of the product (G) and a shape from the second term of the product (K₂); therefore, the vertices u_i in the double cover are shown as circles while the vertices w_i are shown as squares.

The bipartite double cover may also be constructed using adjacency matrices (as described below) or as the derived graph of a voltage graph in which each edge of G is labeled by the nonzero element of the two-element group.