Reading: Read sections 8.4 and 9.1
Exercises:
Prove that a graph with \(n\) vertices and \(m\) edges has at least \(n-m\) connected components.
Say there are \(k\) connected components and each connected component has \(v_i\) vertices in it. Then each connected component has at least \(v_i - 1\) edges in it (if it had this few edges it would be a tree which is minimally connected).
So \(n = \sum_{i=1}^k v_i\) and \(m \ge \sum_{i=1}^k (v_i - 1) = n - k\) so we see that \(k \ge n - m\).
A planar drawing of a planar graph with all vertex degrees exactly 3 has only pentagonal (5-sided) and hexagonal (6-sided) faces. Show that it has exactly 12 pentagonal faces.
Call the planar drawing \(M\), and say that \(M\) has \(v\) vertices, \(e\) edges, and \(f\) faces. Let \(p\) be the number of pentagons and let \(h\) be the number of hexagons in the planar drawing. We know in particular that \(f = p + h\) and \(2e = 5p + 6h\).
We know that the total vertex degree of \(M\) is twice the number of edges, \(\sum_i \deg v_i = 2e\). Since each vertex has degree is exactly 3 we deduce that \(3v = 2e\).
Now Euler’s formula implies that \(6v - 6e + 6f = 12\), and we can manipulate this to see that
\[\begin{align*} 6v - 6e + 6f &= 12 \\ 4e - 6e + 6f &= 12\\ 6f &= 12 + 2e \\ 6p + 6h &= 12 + 5p + 6h \\ p &= 12, \end{align*}\]showing that the number of pentagons must be exactly \(12\).
Prove that if a tree has a vertex of degree \(d\) then it has at least \(d\) leaves.
If \(d = 0\) the statement is vacuously true as all trees have at least 0 leaves. If \(d = 1\) then the tree already has one leaf, the vertex of degree 1.
Say we start with a tree \(T\) that has a vertex \(v\) of degree \(d\). If there is any vertex \(w\) that is a leaf vertex that is not connected to \(v\) by an edge, delete it and its edge (this is the opposite of step (ii) in our growth procedure). This step at no point disconnects the tree, so at some point we will arrive with a “star,” a tree with one central vertex \(v\) of degree \(d\) and \(d\) adjacent leaf vertices.
Notice that the growing procedure can never decrease the number of leaves, as we either attach a new leaf to an old leaf (and the number of leaves is constant) or we attach the new leaf to a non-leaf vertex (and the number of leaves grows by 1). As the original tree can be grown from the \(d\)-star tree with \(d\) leaves by following our sequence of deletions in reverse, the original tree must have at least \(d\) leaves itself.
How many labeled 7-vertex subgraphs of the labeled complete graph on 7 vertices \(K_7\) either have cycles or are disconnected?
There are \(2^{\binom 72}\) 7-vertex subgraphs of the complete graph. Of these, exactly \(7^5\) are both connected and cycle-free (that is to say, trees) So, there are \((2^{\binom 72} - 7^5)\) 7-vertex subgraphs of \(K_7\) that either have a cycle or are disconnected.