Let’s show that: If \(G = (V,E)\) is disconnected, then \(\bar G = (V, \bar E)\) is connected. Let \(a, b\) be vertices in \(V\).
If there is no path between \(a, b\) in \(G\), explain why there is an edge in \(\bar G\) connecting \(a,b\).
There is no path between \(a,b\), so there is no edge \(ab\) in \(G\). But this means there is an edge \(ab\) in \(\bar G\), which is a path between them!
If there is a path between \(a, b\) in \(G\), explain why there is a vertex \(c \in V\) for which there is no path to either \(a\) or \(b\).
Because \(G\) is disconnected, there is a pair of vertices \(v,w\) with no path between them. If \(a,v\) are not connected by a path, let \(c=v\). If \(a,v\) are connected by a path, let \(c=w\). In either case, \(a\) is not connected to \(c\) by a path. Because \(a,b\) are connected by a path, \(b,c\) are not connected by a path either (or else we would have a path from \(a,c\)!).
If there is a path between \(a, b\) in \(G\), explain why there is a path connecting \(a\) to \(b\) in \(\bar G\).
There’s a vertex \(c\) with no paths in \(G\) to \(a\) or \(b\) by part (b). But this means there’s no edges in \(G\) between them. So in \(\bar G\) we have edges \(ac\) and \(bc\) that determine a path between \(a,b\) in \(\bar G\).
Conclude that \(\bar G\) is connected.
In (a) and (c) we determined that there’s a path between \(a,b\) in \(\bar G\) if there was a path between them in \(G\) or if there wasn’t. These are the only two possibilities, so there’s always a path between \(a,b\) in \(\bar G\) if \(G\) was disconnected.
Let \(G\) be connected and cycle-free. Say \(G\) has \(n\) vertices.
Show that if we add a new edge to \(G\) we introduce a cycle.
Consider vertices \(a,b\). Since \(G\) is connected, there is a path between them. Once we add the edge \(ab\), that closes the path into a cycle.
Show that if we remove an edge from \(G\) we disconnect it.
Consider an edge \(ab\). If we remove the edge, and \(a,b\) are still connected by a path, then that path would have closed into a cycle with edge \(ab\). But \(G\) is cycle-free.
Show that \(G\) has at least \(n-1\) edges.
If we have a graph with \(k\) connected components, then adding an edge will either decrease the number of connected components by 1 (connect two components with the edge), or leave it fixed (add the edge within one component).
Start with the edgeless graph on \(n\) vertices; this has \(n\) connected components. Optimally placed, each edge will lower the number of components by \(1\). We need at least \(n-1\) edges to make this graph only have \(1\) connected component.
We’ll prove later in class that \(G\) has exactly \(n-1\) edges. Can you see how you might show that now?
Hint. Show that every such graph with \(n \ge 2\) has at least one vertex of degree 1.