Diameter of a 2-Lift of complete bipartite graph

Question

Give an undirected simple graph $G$ with $n$ vertices and $m$ edges, its 2-Lift is constructed as follows:

• Define $G_1$ to be the original graph $G$. Make a duplicate copy of $G$ and call it $G_2$.
• Now each edge $(u,v)$ in $G$ corresponds to a pair of edges $(u_1,v_1)$ in $G_1$ and $(u_2,v_2)$ in $G_2$.
• For each edge $(u,v)$ in $G$, there are two choices and randomly decides what to do:
  1. Leave each pair of edges as they are: $(u_1, v_1)$ and $(u_2, v_2)$
  2. Make them cross: $(u_1, v_2)$ and $(u_2,v_1)$

As $G$ has $m$ edges, there are $2^m$ possibilities of 2-lifts of $G$. Naturally, there are two extreme cases when the 2-lift is not connected:

• When all the pairs of edges stay as they are, then $G_1$ and $G_2$ are isolated.
• When all the pairs of edges are switched, then we still have two isolated graphs.

Other than these two trivial cases, all the 2-lifts are connected graphs.

The 2-lifts of a graph are recently used for the existential proof of bipartite Ramanujan graphs by Marcus, Spielman, and Srivastava. You may take a look at the visual representation of 2-lifts at the following urls.

• http://www.tcs.tifr.res.in/~prahladh/mysore2013/slides/Srivastava-mp1.pdf
• http://cs-www.cs.yale.edu/homes/marcus/talks/bipartite_ramanujan.pdf

---

Now assume that the original graph $G$ is a complete bipartite graph $K_{n,n}$. Except the two trivial extreme cases, it seems that all the 2-lifts are connected and have diameter 4. (Remember that $dist(u,v)$, the distance of two vertices $u$ and $v$ in a graph, is defined to be the number of edges in a shortest path between $u$ and $v$, and the diameter of a graph is $\max_{u,v}dist(u,v)$.)

Is my conjecture true? If it is, how can I prove it?

Answer 1

Several of your statements, including your conjectures, are untrue.

It is true, that one of the extreme cases (all pairs of edges stay as they are) causes a disconnected graph.

It is (in general) untrue that the other extreme case (all pairs of edges are switched) causes a disconnected graph (even if $G$ itself is connected). A counterexample is already found in the triangle $K_3$. If you switch all pairs of edges the result is a 6-cycle, which is connected.

Your conjecture about connectedness in 2-lifts of complete bipartite graphs is already untrue for certain 2-lifts of the square $K_{2,2}$: if you leave the 'horizontal' pairs of edges untouched and switch the 'vertical' pairs of edges you end up with two 4-cycles, i.e. a disconnected graph.

And then of course the statement about diameter is incorrect as well, since a disconnected graph does not have a finite diameter.