# A bipartite graph

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.

• Unfortunately, the lack of definitions makes it hard to understand what you actually want. Most importantly, I don't understand what it means to be able to "reach" one vertex from another! Does there need to be an edge between them? Or a path? Or an edge/path with special properties? – Ingix Jan 7 '19 at 18:29
• @Ingix think that's true. I'll add some pictorial representations. – resound Jan 7 '19 at 19:08
• In a tree, the partition of the vertices into two sets $V_1$ and $V_2$ such that all edges have one endpoint in $V_1$ and the other in $V_2$, is unique--up to which set is $V_1$ and which of the other is $V_2$; namely, for any vertex $v$, let $V_1$ be the set of vertices of odd distance from $v$ and $V_2$ be the set of vertices of even distance away (each edge assumed to have unit length). You can check this is the same partition (up to which set is $V_1$ and the other $V_2$) no matter $v$. A forest with $c$ connected components has $2^{c-1}$ such partitions of the vertices. Can you see why? – Mike Jan 7 '19 at 19:21
• @ingix Here's the added image. – resound Jan 7 '19 at 19:45
• @Mike Here's added image. Maybe this will clear my question – resound Jan 7 '19 at 19:45

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.

• I see, then the optimum answer is always 2 ? Also, any source for this information that may provide code for this. I am still new to Graph Algorithms. Thank you so much for this answer! @MishaLavrov – resound Jan 8 '19 at 17:43
• What sort of source are you looking for? – Misha Lavrov Jan 8 '19 at 17:44
• For the purposes of writing code, only the last two paragraphs are relevant. Handle the case of a star separately; for non-star trees, just move $\frac{|A|-|B|}{2}$ leaves from $A$ to $B$ if $|A|>|B|$, or $\frac{|B|-|A|}{2}$ leaves from $B$ to $A$ if $|A|<|B|$. The rest is just my proof that you won't run out of leaves when you do so. – Misha Lavrov Jan 8 '19 at 17:45
• By source I meant.. some algorithmic page with such content maybe. I thought this was kind of something standard, but now I think it's more of an ad-hoc problem. I think I'll try implementing this. Thank you again! @MishaLavrov – resound Jan 8 '19 at 17:48
• It's not impossible that people have looked at this problem before, but I'm not aware of it. (And searching for balancing trees gives a lot of unrelated results about binary search trees.) – Misha Lavrov Jan 8 '19 at 17:54

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.

• It's true that by the rearrangement that you've shown, it's possible to reach every vertex from any other, but then, we also need that there must be equal elements in the two sets(stated in the OP). So by adding the extra edges, it's true that it is no more a Tree, but that is what the question is. We may destroy the presence of a tree by adding edges, but it's necessary to have equal number of elements in the two matching sets. I am really sorry for bad phrasing and thank you so much for such consideration @Ingix – resound Jan 8 '19 at 17:30
• The other answer's formal wording is actually what I exactly meant. @Ingix – resound Jan 8 '19 at 17:35