MA 415G course notes

There are two cases to consider. Suppose we add a new edge \(e=\{x,y\}\) to \(G\text{.}\) If \(x\) and \(y\) are already in the same connected component, then adding \(e\) does not change any components. However, if \(x\) and \(y\) are in different components, then adding \(e\) will merge the components containing \(x\) and \(y\) into a single component, since now any vertex connected by a path to \(x\) is also connected by a path to \(y\text{.}\) Thus, this will reduce the number of connected components by one.

Suppose \(G\) is a graph on vertex set \([n]\text{.}\) We construct \(G\) by starting with the empty graph, i.e., the graph on \([n]\) with no edges, and adding the edges of \(G\) one at a time. Note that in this case, each individual vertex forms a connected component, hence the empty graph has \(n\) components. In order for \(G\) to be connected, every element in \([n]\) must be connected to every other element by a path. Thus, in the process of adding edges one at a time to create \(G\text{,}\) we must merge \(n\) components into a single component. Each time we add an edge, either there are no components merged or the number of components reduces by one. In order to get from \(n\) components to one component, we must merge \(n-1\) times, which requires at least \(n-1\) edges be added.

Suppose \(G\) is a connected graph and \(e=\{x,y\}\) is a new edge added to \(G\text{.}\) There exists a simple path in \(G\) from \(x\) to \(y\text{,}\) and connecting the endpoints of the path using \(e\) creates a cycle.

We will use the following logical implications to prove the classification:

First, we will prove that if \(G\) is connected and acyclic then it also has \(n-1\) edges. Construct \(G\) by starting with the empty graph and adding one edge at a time. Each time we add an edge, if the edge bridges two different connected components, then it merges those components and does not introduce any new cycle. If an edge is added where both of the endpoints of the edge are in the same connected component, then by Lemma 3.3.18 this introduces a cycle. However, \(G\) is acyclic, and therefore this cannot happen. Thus, every new edge added results in a merging of components and by the argument in Lemma 3.3.16, this results in \(n-1\) edges.

Second, we will prove that if \(G\) is connected with \(n-1\) edges, then it is acyclic. Suppose that \(G\) does contain a cycle \(C\text{.}\) Then removing one of the edges in \(C\) will not disconnect \(G\text{,}\) since the endpoints of the edge are still connected by the remaining edges of \(C\text{.}\) However, this will result in a graph that is connected with \(n-2\) edges, which is impossible by Lemma 3.3.16. Therefore, the original graph must be acyclic.

Finally, we will prove that if \(G\) is acyclic with \(n-1\) edges, then it is connected. We again construct \(G\) by starting with the empty graph and adding edges one at a time. Each time we add an edge, we must add an edge that results in the merging of two connected components, as otherwise Lemma 3.3.18 implies that there is a cycle, which is not possible since \(G\) is acyclic. Therefore, we add \(n-1\) edges, and each of these edges results in the merging of two connected components. We begin with the empty graph, having \(n\) components, and thus the result is a graph with one component, which is the same as being connected.