Question

Show that every tree is bipartite.

Short answer

Therefore, every tree is bipartite is the true statement.

Step-by-step solution

General form

Definition of tree: A tree isa connected undirected graph with no simple circuits.

Definition of Circuit:It isa path that begins and ends in the same vertex.

Bipartite graph (Definition): It is a simple graph whose vertices can be partitioned into two sets \({{\bf{V}}_{\bf{1}}}\) and \({{\bf{V}}_{\bf{2}}}\) such that there are no edges among the vertices of \({{\bf{V}}_{\bf{1}}}\) and no edges among the vertices of \({{\bf{V}}_{\bf{2}}}\), while there can be edges between a vertex of \({{\bf{V}}_{\bf{1}}}\) and a vertex of \({{\bf{V}}_{\bf{2}}}\).

Definition of Level: The level of a vertex is the length of the path from the root to the vertex.

Proof of the given statement

Given that, T is a tree.

To prove: T is bipartite.

Let \({{\bf{V}}_{\bf{1}}}\) contains all vertices at level 0, level 2, level 4, etc., of the tree T and let \({{\bf{V}}_{\bf{1}}}\) contains all vertices at level 1, level 3, level 5, etc.,

There cannot be edges from a vertex in \({{\bf{V}}_{\bf{1}}}\) to a vertex in \({{\bf{V}}_{\bf{1}}}\), as a vertex at level h can only be connected to a vertex at level h-1 or level h+1.

Similarly, there cannot be edges from a vertex in \({{\bf{V}}_{\bf{2}}}\) to a vertex in \({{\bf{V}}_{\bf{2}}}\), as a vertex at level h can only be connected to a vertex at level h-1 or level h+1.

Finally, it is possible that there are edges from a vertex in \({{\bf{V}}_{\bf{1}}}\) to a vertex in \({{\bf{V}}_{\bf{2}}}\).

Conclusion: So, the graph is bipartite.

Hence proved.