We can apply the idea of a tree as a minimally connected graph to say something about connectivity in graphs in general. One clear application is finding a minimal connected subgraph of the graph such that every vertex is connected. One can see how this might be useful in something like road network where you’re trying to figure out what the most important roads to clear after a snowfall are.
A spanning subgraph which is also a tree is called a spanning tree.
Here is a graph, with one possible spanning tree highlighted.
A graph $G$ is connected if and only if it has a spanning tree.
Suppose $G$ has a spanning tree $T$. Then there exists a path between every pair of vertices in $T$ and therefore, there exists a path between every pair of vertices in $G$. Then by definition, $G$ is connected.
Now, suppose $G$ is connected. Consider the connected spanning subgraph $H$ of $G$ with the minimal number of edges. Suppose $H$ contains a cycle. Then we can remove an edge from this cycle, since no edge in a cycle is a bridge. Therefore, $H$ contains no cycles and since $H$ is connected, it is a tree.
An obvious computational problem is to find or construct spanning trees for a given graph. Many of you already know the algorithms that do this—it’s breadth and depth first search. We are already familiar with BFS and DFS as algorithms that solve the connectivity problem: given two vertices $s$ and $t$, is there a path from $s$ to $t$?
This may not be something that you’ve considered before, particularly since we typically teach these as algorithms on directed graphs. Of course, the same algorithms work perfectly fine on undirected graphs. But notice that both of these algorithms visit every reachable vertex and only visit each vertex exactly once. This means that the traversal that these algorithms take is acyclic. And that we can reach every reachable vertex gives us an acyclic spanning subgraph for the component that contains $s$.
Recall that a graph is bipartite if its vertex set can be partitioned into two sets so that all of the edges of the graph only travel between these two sets.
Bipartite graphs come up naturally in a lot of applications because a bipartite graph models relationships between two groups of things: job applicants and potential employers, PhD students and PhD advisors, pigeons and pigeonholes, etc. In many of these applications, we would like to assign or match an object from the first set with an object from the second. This leads to the following notion.
A matching in a graph $G = (V,E)$ is a subset of edges $M \subseteq E$ such that no two edges in $E$ share the same incident vertex. A vertex that is incident to an edge in a matching $M$ is matched or saturated in $M$; otherwise, it is unmatched.
Consider the following graph. Here, $M = \{(1,8), (2,6), (3,7)\}$. So vertices $1 ,2, 3, 6, 7, 8$ are matched, while vertices $0, 4, 5$ are unmatched.
A matching $M$ for a graph $G = (V,E)$ is said to be
The above definitions distinguish between maximal and maximum matchings. Just because you have a matching that can’t be expanded doesn’t mean that you necessarily have the largest possible matching!
Note that in our earlier example, $M$ was a maximal matching—no edges can be added to the matching without violating the matching condition. However, this graph can exhibit a larger matching:
Since every vertex on the bottom is matched, this is a complete matching, and therefore, it is also a maximum matching. However, other maximum matchings exist for this graph.
This matching also happens to be complete for one side of the bipartition. We would obviously like to be in this case whenever possible—obviously when both partitions are the same size, that would be great, but if not, then we would like this even just for the smaller side.
When might we not have a complete matching? Let’s say we’re matching students to internships. If we look at some subset of students, say four or five of them, and they’re only interested in two or three positions, then there’s no way that they’ll all get a position. So we can’t find a complete matching for students. For instance, consider the following graph.
We see that if we try to match even just $0, 1, 2$, we are unable to do so.
First, let’s formally define the set of vertices adjacent to a given vertex. Such vertices are neighbours, so we will call the set of neighbours a neighbourhood.
Let $G = (V,E)$ be a graph. The neighbourhood of a vertex $v \in V$ is the set of neighbours of $v$, \[N(v) = \{u \in V \mid (u,v) \in E\}.\] We can extend this definition to sets of vertices $A \subseteq V$ by \[N(A) = \bigcup_{v \in A} N(v).\]
Then it turns out the example we described is necessary and sufficient for a complete matching if we do this check for all subsets of vertices. This is Hall’s Theorem.
Let $G = (V,E)$ be a bipartite graph with bipartition $(V_1, V_2)$. Then $G$ has a complete matching for $V_1$ if and only if $|N(A)| \geq |A|$ for all subsets $A \subseteq V_1$.
The proof of this is quite lengthy and it proceeds by strong induction. You can find it in the textbook.