Show by induction that every tree is bipartiteSolutionProff

Show by induction that every tree is bipartite

Solution

Proff;- Let tree T contains a vertex v of degree 1,

Clearly when |T| = 1, T is bipartite ,   and that T v is also a tree.

Now by induction on the number n of vertices of a tree T.

the complete bipartite graph Ka,b is a bipartite graph in which every possible edge between the two sets exists

For n = 1, 2, the only trees are K1 and K2 and both are bipartite.

Suppose that any tree on less than n vertices is bipartite and let T be a tree on n vertices.

Let v be a vertex of degree 1 in T and let u be its only neighbor.

We know that T v is a tree with n 1 vertices,

so, by induction assumption, T v has bipartition X, Y .

(This means that every edge in T v has one endpoint in X and the other one in Y .)

Now, if u X, then X, Y {v} is a bipartition of T. However, if u Y , then Y, X {v} is a bipartition of T.

Hence its prove that every tree is bipartite.