A tree is always a Bipartite Graph as we can always break into two disjoint sets with alternate levels. In other words, we always colour it with two colours such that alternate levels have the same colour. The task is to compute the maximum no. of edges that can be added to the tree so that it remains Bipartite Graph.
1) Do a simple DFS (or BFS) traversal of the graph and colour it with two colours.
2) While colouring also keep track of counts of nodes coloured with the two colours. Let the two counts be count_color$_0$ and count_color$_1$.
3) Now we know maximum edges a bipartite graph can have are count_color$_0$ x count_color$_1$.
4) We also know tree with n nodes has n-1 edges.
5) So our answer is count_color$_0$ x count_color$_1$ – (n-1).
Time Complexity : $O(n)$ where n is the number of vertices
$\therefore $ The answer is $C$
