A bipartite graph

Question

We know that all trees are bipartite. Suppose the vertices of the tree when converting to a bipartite graph belong to the two sets A and B. It is not important that the number of vertices in the two sets are same. Also, it's not important that it is possible to reach every vertex in A from any vertex in B. Suppose we need to build a kind of Complete bipartite graph, in the sense that we can reach any vertex in A from B or reach any vertex in B from A and that the number of vertex in A is equal to B. Obviously, this is fairly simple by adding vague edges in the tree, which will fulfill our purpose but definitely it won't be a tree now because of the cycles created.

Let's suppose we are allowed to destroy the tree, but not by adding vague edges but can only add edges of the smallest length possible. That means, if we can get such a Complete Bipartite graph by adding an edge of length $3$ between one or maybe more vertex, then I may add edges of length less than $3$ or equal to $3$ but not more than that, because it's unnecessary. Unit length here would represent two adjacent vertex distance. So, if I cross two vertexes when I move from vertex $x$ to vertex $y$ then the length between $x$ and $y$ is $3$.

Now, about how I'm thinking: I think we just need to create one vertex in A that has an edge to every vertex in B and having one vertex in B that has an edge to every vertex in A. This way it's possible to reach any vertex in any set. It's obvious that we need to add some edges to keep equal number of elements in set A and B, but by the way I just stated, I think that will require adding least number of edges and hence maybe helpful in adding smaller edges altogether. Correct me, if I am wrong but I am unable to decide how to begin with this.

P.S. Complete Bipartite graph is just a name used here and has nothing to do with the term's original meaning.

Image Link : https://ibb.co/bdqSnwk

Answer 1

Let's see if I understand the problem correctly. Given a tree $T$ on $2n$ vertices, you want to create a bipartite graph $G$, on the same vertex set, with bipartition $(A,B)$ such that $|A|=|B|=n$. You want $G$ to be connected, but you want each edge in $G$ to join two vertices at distance at most $k$ in the tree $T$, for the least possible $k$.

---

Here is the optimal way to do this, which achieves $k=2$. Start with the ordinary bipartition of $T$. Suppose that in this bipartition $|A|>|B|$.

In this case, set aside all the leaves (degree $1$ vertices) of $T$ that are in $A$; let $A'$ be the set of all non-leaves. We show that there's a matching between $A'$ and $B$ that saturates $A'$: a set of edges of $T$ that include every vertex of $A'$ exactly once, and every vertex of $B$ at most once.

To find the matching, let $u \in A'$ be an arbitrary vertex. Each other vertex $v \in A'$ has at least two neighbors, only one of which lies on the path from $u$ to $v$; pick one that does not lie on that path, and match it to $v$. (We can match $u$ with any neighbor we like.) Two vertices $v_1, v_2 \in A'$ cannot be matched to the same vertex $w \in B$; if so, then there are two paths from $u$ to $w$ (one through $v_1$ and one through $v_2$) which contradicts the definition of a tree. So no vertex of $B$ is used multiple times, and we've found a matching from $A'$ to $B$.

(Exercise: this step could also have been done using Hall's theorem!)

In particular, this means that $|A'| \le |B|$. Since $|A| > |B|$, we know that the difference $|B|-|A|$ is at most the number of leaves in $A$.

Now move leaves from $A$ to $B$ one at a time until $|A|=|B|$. When we move a leaf $u$ from $A$ to $B$, we need to connect it back to the tree; to do this, let $v$ be $u$'s only neighbor ($v \in B$) and let $w$ be any non-leaf neighbor of $v$ ($w \in A$). Add the length-$2$ edge $uw$; now the graph is connected again.

This works for all trees except a star: a tree in which all vertices except one are leaves. In this case, the last step fails because the vertex $v$ has no non-leaf neighbors. But in the star, all distances are at most $2$, so any way we decide to balance it will work.

Answer 2

I'm still not sure what exactly you want, but I feel that further progress can be made only with a dialog that is not possible in comments.

Look at the following picture

It is the graph (tree) that you called "normal tree" in your picture, just slightly rearranged. It is in "bipartite form", with one class of vertices on the left and the other on the right.

You can reach each vertex from any other, as this is a connected graph. So if you (dsfx) could explain on this example what the purpose is of adding extra edges that might shed a light on your problem.

+++++

In your picture, when you show the bipartite graph, there are only 2 "continuous" (original, I assume) edges. However, since you have 6 vertices, that does not create a tree. This would be a forest, consisting of one tree with 3 vertices (and 2 edges) and 3 trees with one vertex (and no edge). Maybe that is the source of the confusion here.