Doubt on Bipartite Graph

Question

What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph?

---

Now my question is, why do we need to add  edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??

Comments

They are asking how many max edges can we add such that the original tree is still  a bipartite graph.
See here :
https://www.geeksforgeeks.org/maximum-number-edges-added-tree-stays-bipartite-graph/

Answer 1

Since it is a tree, choose any arbitrary node as root. Apply BFS at the root.Alternatively color the nodes at each level with red and black color.

Max edges=No.of red nodes $\times$ No. of black nodes - no.of edges in the tree.

You can do it in $O(n)$. Since it is a tree , there will be n-1 edges, if there are n vertices.

Comments

tree is already bipartite. Then where do we add those edges??

---

See, suppose the vertex set={$1,2,3,4,5$}

Edge-set={$(1,2)$,$(1,3)$,$(2,4)$,$(3,5)$}

On applying BFS, you would see that the color of 1 is red, of 2 and 3 is black,4 and 5 is red.

Therefore the partite sets are :-{$1,4,5$} and {$2,3$}.

How many possible edges can be there between these partite sets ? |{$1,4,5$}| $\times$ |{$2,3$}|=

$3 \times 2 =6$.

Number of edges already existing in the bipartite graph=|Edge-set|=4.

How many edges can we add ? 6-4=2.

Please comment if some part is still unclear.