A tree is a connected graph with no cycles. A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set.

To show that every tree is a bipartite graph, we can use induction on the number of vertices in the tree.

Base case: A tree with one vertex is trivially bipartite.

Inductive step: Assume that every tree with n vertices is bipartite. Let T be a tree with n+1 vertices. We can construct a bipartite graph from T by taking one vertex as one part of the bipartition and the remaining n vertices as the other part. The edges of the bipartite graph are the same as the edges of T.

By induction, every tree is a bipartite graph.