Skip to main content

Chapter 2 Trees and Bipartite Graphs

It is often helpful to restrict our attention to a nice class of graphs. In this chapter, we will consider two such classes: trees and bipartite graphs. In addition to their usefulness in applications, these classes of graphs will serve as a nice proving ground for proof techniques in graph theory.

Definition 2.0.1.

A tree is a connected graph with no cycles. A forest is a graph with no cycles.

Although it is not explicit in the definition, it should be clear that a forest is the union of disjoint trees.

First, assume G is a tree. Since G is connected, there is at least one path between any two vertices in G. To show that path is unique, suppose not such that there exists another path between vertices in G. For both paths to exist, they must both start and end at sames vertices, but must also diverge from one another to make them distinct. Those diverging paths will eventually come back together since the paths must end at the same vertex. This creates a cycle, but trees are defined to be cycle free, thus yielding a contradiction. Therefore the path between any two vertices in a tree is unique.

Second, in a connected graph, G, assume the path between any two vertices is unique. A tree is defined to be connected and cycle free. For any two vertices in a cycle, there exists at least two unique paths between vertices, but by our assumption, there is only one unique path between vertices, meaning that G must be cycle free. Since G is cycle free and we assumed that G was connected, G must be a tree.

If you have a graph that is not a tree, you could start removing edges in the hopes of finding a spanning subgraph that was a tree. Depending on which edges you remove, this spanning tree might look different. One question you might ask is how many edges, at a minimum, you would have to remove to get a tree (and whether this minimum number depends on which edges you start removing).

On the other hand, you might start with a non-tree graph and build a spanning tree by including as few edges as possible (sort of building the tree up, rather than pruning the graph down to a tree).

Definition 2.0.3.

A spanning tree in a graph \(G\) is a subgraph that is a tree and spans (i.e., has the same vertex set as \(G\)).

Let \(G\) be a connected graph, and suppose that \(G\) has no cycles. Then \(G\) is its own spanning tree. Now suppose that \(G\) does in fact contain cycles. Then for any subgraph of \(G\) that is a cycle, we can preserve the set of vertices and remove one edge from the set of edges constituting the cycle. Removing an edge in this way from each cycle in the graph \(G\) thus removes all cycles, while preserving connectedness between each point and preserving the set of vertices of \(G\text{.}\) Thus \(G\) contains a spanning subtree.

But must all spanning trees have the same number of edges? What is the relationship between the number of vertices and number of edges in a tree? What are the possibilities?

For a single vertex we have that \(p=q+1\text{.}\)

Assume that all trees with \(n\) vertices have \(n+1\) edges.

Consider an arbitrary tree, \(T\text{,}\) with \(n+1\) vertices. Since \(T\) is connected \(\delta(T) \ge 1\text{.}\) Since \(T\) has not cycles \(\delta(G) \lt 2\) (Proposition 1.3.5). So \(T\) has at least on vertex of degree 1, say \(x\text{.}\) Remove \(x\text{.}\) Since \(d(x)=1\) it cannot be on the path between any two other vertices so \(T-x\) is a tree with \(n\) vertices. Then \(T-x\) has \(n-1\) edges. \(T\) has one more edge than \(T-x\text{.}\) So \(T\) has \((n+1)+1\) edges.

What about the converse of Theorem 2.0.5? If a graph satisfies that relationship between \(p\) and \(q\text{,}\) must it be a tree? If not, what additional criteria would be required?

Theorem 2.0.5 can be used to deduce facts about graphs in a variety of ways. Here are a few examples.

Example 2.0.6.

Suppose \(G\) is a tree in which the average degree is \(1.98\text{.}\) How many vertices does \(G\) have?

Solution

Suppose \(G\) is a tree in which the average degree is \(1.98\text{.}\) Suppose further that \(G\) has \(p\) vertices and \(q\) edges. We know the average degree, \(d(G)\text{,}\) is given by \(\frac{2q}{p}\text{.}\) Because \(G\) is a tree, we also know \(q=p-1\text{.}\) So, \(1.98=\frac{2(p-1)}{p}\text{.}\) Solving for \(p\) gives that \(p = 100\text{.}\) That is, the number of verticies must be \(100\text{.}\)

Example 2.0.7.

How many cycles can a connected graph with average degree 2 have? What if the average degree is less than 2?

Solution

Suppose that \(G\) is a connected graph with \(n\) vertices \({v_1, ..., v_n}\text{.}\) Suppose that \(\frac{deg(v_1)+...+deg(v_n)}{n}=2\text{.}\) Then \(deg⁡(v_1 )+ ...+deg⁡(v_n ) = 2n\text{.}\) This implies that the number of edges in \(G\) is \(n\text{.}\) This is because \(deg⁡(v_1 )+ ... +deg⁡(v_n)\) counts every edge exactly twice, one for each end point. Therefore \(G\) is not a tree because there are \(n\) vertices and \(n\) edges and a tree must have one more vertex than edge. So \(G\) has at least 1 cycle. \(G\) is connected so within \(G\) there exists a spanning tree, \(T\) with \(n\) vertices and \(n-1\) edges. Let \(e\) be the edge from \(G\) that is not in \(T\) and let \(e\) go between vertices \(v_i\) and \(v_j\text{.}\) In \(T\text{,}\) there is a unique path \(P_1\) between vertices \(v_i\) and \(v_j\) (Theorem 2.0.2). The union of \(P_1\) and \(e\) will form a cycle. Call this cycle \(C_1\text{.}\) Suppose that there is another cycle \(C_2\) in \(G\text{.}\) If \(C_2\) does not contain \(e\) then this contradicts the fact that \(T\) is a spanning tree. If \(C_2\) contains \(e\) then we can write \(C_2\) as the union of \(e\) and a different path \(P_2\) within \(T\) between vertices \(v_i\) and \(v_j\text{.}\) However, this contradicts Theorem 2.0.2 (A graph is a tree if and only if there exists exactly one path between any pair of vertices). Hence, a connected graph \(G\) with average degree of 2 contains exactly 1 cycle. Now, suppose that \(G\) is a connected graph with \(n\) vertices \({v_1, ..., v_n}\text{.}\) Suppose that \(\frac{deg(v_1)+...+deg(v_n)}{n} \lt 2\text{.}\) Then \(deg⁡(v_1 )+ ...+deg⁡(v_n ) \lt 2n\text{.}\) Because \(G\) is connected it has a spanning tree, \(T\) with \(n\) vertices \({v_1,...,v_n}\text{.}\) By Theorem 2.0.5 a tree with \(n\) vertices will have \(n-1\) edges, \(E\text{.}\) So, within the spanning tree, \(T\text{,}\) the \(deg⁡(v_1 )+ ⋯ +deg⁡(v_n) \lt 2|E|=2(n-1)\) because in \(deg⁡(v_1 )+ ⋯ +deg⁡(v_n)\) each edge is counted exactly twice, once for each endpoint. Hence, in the spanning tree \(T\text{,}\) \(\frac{deg(v_1)+...+deg(v_n)}{n} = \frac{2(n-1)}{n}\text{.}\) Now if the spanning tree, \(T\) is the same as the graph \(G\) then we are done. A connected graph with average degree less than 2 is a tree and therefore has no cycles. To get a contradiction suppose \(G \ne T\text{.}\) There must exists an edge in \(G\) which is not in \(T\text{.}\) Call this edge \(e\text{.}\) The addition of edge \(e\) increases the total number of edges by 1. Hence, \(G\) has \(n\) vertices and \((n-1)+1=n\) edges (the edges from \(T\) plus edge \(e\)). The average degree of \(G\) then becomes \(\frac{deg(v_1)+...+deg(v_n)}{n} = \frac{2(n)}{n} = 2\text{.}\) This contradicts the assumption that \(G\) has an average degree of less than 2. Therefore \(G=T\) and by the definition of a tree \(G\) has no cycles. Hence, a connected graph \(G\) with average degree strictly less than 2 has no cycles and is in fact a tree.

Example 2.0.8.

Suppose \(G\) is a tree in which every vertex has odd degree. Prove that \(G\) has an odd number of edges.

Solution

We know that \(|E|=\frac{\sum\limits_{v_i\in V}d(v_i)}{2}\) Then, since we know that all \(d(v_i)\) are odd, we know that we must be summing an even number of degrees to be divided by 2 and get an integer.

So it must be true that \(|V|\) is even. Then because it is given that \(G\) is a tree we know that \(|E|=|V|-1\) and since \(|V|\) is even, this implies that \(|E|\) is odd.

Given the results above, we can now conclude the following.

Let \(G\) be a connected graph with \(p\) vertices and \(q\) edges. If \(G\) is a tree, then we have that \(p=q+1\) by Theorem 2.0.5 and we're done. Then suppose that \(G\) is not a tree. But \(G\) is connected, so by Proposition 2.0.4 \(G\) contains a spanning tree, say \(G'\text{.}\) Then \(G'\) has \(p\) vertices and \(q'=q-l\) edges, \(1\leq l\lt q\text{,}\) and satisfies \(p=q'+1 \) since \(G'\) is a tree. But then we have \(p=q'+1=q-l+1 \text{,}\) so then \(p\lt q+1\text{.}\) Thus if \(G\) is a connected graph with \(p\) vertices and \(q\) edges, then \(G\) satisfies \(p \leq q+1 \text{.}\)

Now consider bipartite graphs. The idea is that it is sometimes possible to partition the vertices of a graph into two sets so that there are no edges between pairs of vertices within either set. Let's try to give a slightly more precise definition.

Definition 2.0.10.

A graph \(G\) is bipartite provided the set of vertices in \(G\) can be decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent.

There is a connection between trees (and forests) and bipartite graphs.

First we will show that every tree is bipartite with induction on the number of vertices, \(n\text{.}\) First notice that in any tree with \(n \ge 2\) will have at least 2 vertices of degree 1 or leaves.

Base Case: \(n=1\text{.}\) This a bipartite graph, one of the sets is just the empty set.

Inductive step: Suppose that we know that every tree with \(n\) nodes is bipartite, for some \(n \ge 1\text{.}\) Let \(T\) be a tree with \(n+1\) nodes. We will try to show that \(T\) is bipartite. Since \(n+1 \ge 2\) we know that \(T\) has a leaf, \(v\text{.}\) Let \(w\) be the unique adjacent vertex of \(v\text{.}\) Let \(T'=T-{v}\text{.}\) Note that \(T'\) is still a tree because it is connected and had no cycles. Using the induction hypothesis, \(T'\) is bipartite and can be split into two disjoint sets \(A'\) and \(B'\) such that no two vertices within the same set are adjacent. Then we will try to split the vertices of \(T\) into two disjoint sets: \(A\) and \(B\text{.}\) If \(u\) is a vertex of \(T\) not equal to \(v\text{,}\) place \(u\) in the set that it was in the \(T'\text{.}\) Then put \(v\) in whatever set we did not put \(w\text{,}\) its neighbor in. Then we have successfully split \(T\) into two disjoint sets \(A\) and \(B\) such that no two vertices within the same set are adjacent. Hence tree \(T\) is a bipartite graph.

A forest is a disconnected, acyclic graph. In other words, a disjoint collection of trees. Therefore, each component of a forest is tree. So, we can individually partition each component tree into two disjoint sets because trees are bipartite. Then let the disjoint sets of the overall forest be the union of the disjoint sets from each tree component. Hence every forest is also bipartite.

We can find a faster proof of the previous result if we first prove the following about bipartite graphs and the lengths of their cycles.

Since \(G\) is bipartite, we can split the vertices into two disjoint sets \(A\) and \(B\) where each edge of \(G\) joins a vertex of \(A\) and a vertex from \(B\text{.}\) Without loss of generality, let \(v_1 v_2…v_m v_1\) be a cycle in \(G\) where \(v_1\) is in \(A\text{.}\) This then means that \(v_2\) is in \(B\text{,}\) \(v_3\) is in \(A\text{,}\) so on and so forth until \(v_m\) which must be in \(B\text{.}\) Hence the cycle length is even. Assume that every cycle in \(G\) is of even length. Let \(v\) be a vertex in \(G\text{.}\) Next divide the vertices of \(G\) into two sets. Set \(A\) where the shortest path from any vertex in \(A\) to \(v\) is of odd length and set \(B\) where the shortest path from any vertex in \(B\) to \(v\) is of even length. Notice, this means that \(v\) is in set \(B\) and no vertex of \(G\) is in both sets. To draw a contradiction, suppose that \(v_i\) and \(v_j\) are adjacent vertices in set \(A\text{.}\) Then there would be an odd cycle \(v...v_i v_j ...v\) which contradicts that all cycles in \(G\) are of even length. Therefore, that \(v_i\) and \(v_j\) cannot be adjacent vertices in set \(A\text{.}\) A similar argument can be shown for set \(B\text{.}\) Hence \(G\) can be decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent and thus is bipartite.

Note that since trees have no cycles, they have no odd cycles, so every cycle contained is even. Thus every tree is bipartite.