Show that every tree is a bipartite graph. Construct an example of a bipartite…

Concept

A graph G = (V, E) is bipartite when its vertex set can be split into two disjoint parts X and Y so that every edge of G has one endpoint in X and the other in Y; no edge is allowed to join two vertices lying in the same part. Equivalently, by the odd-cycle characterisation, a graph is bipartite if and only if it contains no cycle of odd length. A tree, on the other hand, is a connected acyclic graph, and in a tree there is exactly one path between any two vertices. Bipartiteness is a colouring property (a proper 2-colouring of the vertices), whereas being a tree is a structural property (connected and acyclic), so the two notions are not interchangeable: the argument below shows one direction holds always, and the counterexample shows the other direction fails.

Application 1 - every tree is bipartite

Let T = (V, E) be a tree. The proof constructs the two parts explicitly from distances to a root.

1. If T has at most one vertex it has no edge, and the partition (V, empty set) is vacuously a bipartition, so assume T has at least one edge. Fix any vertex r of V and call it the root.

2. For each vertex v define d(v) as the number of edges on the r-v path in T. This is well defined: T is connected, so such a path exists, and T is acyclic, so that path is unique.

3. Define X = { v in V : d(v) is even } and Y = { v in V : d(v) is odd }. Every integer is either even or odd and never both, so X and Y are disjoint and their union is V.

4. Take any edge uv of E and let P be the unique r-u path. Either v already lies on P, in which case v must be the neighbour of u on P and d(v) = d(u) - 1; or v does not lie on P, in which case P followed by the edge uv is an r-v path, and by uniqueness it is the r-v path, giving d(v) = d(u) + 1.

5. In both cases d(u) and d(v) differ by exactly 1, so they have opposite parity. Hence one endpoint of uv lies in X and the other lies in Y.

6. Since this holds for every edge, no edge of T joins two vertices of the same part, so (X, Y) is a bipartition of T. Therefore every tree is bipartite.

Cross-check of Application 1

The same conclusion follows in one line from the odd-cycle characterisation: a tree contains no cycle at all, hence in particular no cycle of odd length, hence it is bipartite. The distance argument above is the constructive version of that statement, because it actually exhibits the two parts as the even-level and odd-level vertices.

Application 2 - a bipartite graph that is not a tree

Take the 4-cycle C4 on the vertices a, b, c, d with the four edges ab, bc, cd and da, and set X = { a, c } and Y = { b, d }.

• It is bipartite: every one of the four edges has one endpoint in X and one in Y, as the table shows, and neither part carries an edge inside it.

• It is not a tree: a-b-c-d-a is a cycle, while a tree is by definition acyclic. The edge count confirms it, since C4 has n = 4 vertices and 4 edges, whereas every tree on n vertices has exactly n - 1 = 3 edges.

• It is consistent with the criterion: the only cycle here has length 4, which is even, so the odd-cycle criterion independently certifies bipartiteness.

Result

Every tree is bipartite, but the converse fails: C4 above, any even cycle C2k, the complete bipartite graph K2,3, or a disconnected graph formed by two independent edges are all bipartite and none of them is a tree. Trees therefore form a proper subclass of the bipartite graphs - a bipartite graph may contain cycles, provided every cycle has even length, and it may also be disconnected.