How to Prove Every Tree is a Bipartite Graph

Understanding the concept of a bipartite graph and its relation to a tree can provide a powerful tool in graph theory. A bipartite graph is defined as a graph where the vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. On the other hand, a tree is a connected graph that contains no cycles. In this article, we will explore how to prove that every tree is indeed a bipartite graph.

Definitions

Tree

Formally, a tree is a connected graph without cycles. It is a fundamental structure in graph theory, widely used in various applications such as network analysis, data structures, and algorithm design.

Bipartite Graph

A bipartite graph is a graph where the vertex set can be split into two disjoint sets such that no two vertices within the same set are connected by an edge. This article will show how to apply this definition to prove that every tree is a bipartite graph.

Proof by Induction

To prove that every tree is a bipartite graph, we can employ mathematical induction. The proof is structured into three main parts: the base case, the induction hypothesis, and the induction step.

Base Case

Consider a tree with a single vertex, denoted as (T_1). This tree is trivially bipartite because we can assign the single vertex to one set, and there are no edges to violate the bipartite condition.

Induction Hypothesis

Assume that any tree with (n) vertices is bipartite. We will use this hypothesis as the basis for our induction step.

Induction Step

Now consider a tree (T) with (n 1) vertices. Since (T) is a tree, it must have at least one leaf (a vertex with degree 1). Let's denote this leaf vertex as (v). Removing (v) and the connecting edge from (T) results in a tree with (n) vertices, denoted as (T').

Applying the Induction Hypothesis

By the induction hypothesis, since (T') is a tree with (n) vertices, it can be colored with two colors, say color 1 and color 2, such that no two adjacent vertices share the same color.

Adding Back the Leaf

Now we need to add the leaf vertex (v) back to the graph. Since (v) was connected to only one vertex (u) in (T'), we can assign (v) a color different from that of (u). Specifically, if (u) is colored with color 1, then (v) will be colored with color 2, and vice versa. This ensures that no two adjacent vertices share the same color.

After adding (v) back into the graph, no two adjacent vertices share the same color, thus (T) is bipartite.

Conclusion

Since we have shown that the base case holds, and if a tree with (n) vertices is bipartite, then a tree with (n 1) vertices is also bipartite, we conclude by induction that every tree is a bipartite graph.

Alternative Characterization

Another way to see this is by noting that trees can be colored using two colors in a breadth-first search (BFS) or depth-first search (DFS) manner. Starting from any vertex, color it with one color, then color all its neighbors with the other color, and continue this process. This method also confirms that no two adjacent vertices will have the same color, confirming that trees are bipartite.

Understanding and proving that every tree is a bipartite graph provides a rich foundation in graph theory. This property has numerous applications and encourages further exploration in the realm of graph algorithms and structures.