Section 3: Proofs Flashcards
Let F be a forest. Prove that every connected component of F is a tree.
Let H be an arbitrary connected component of F. We want to
show that H is a tree, so we must demonstrate that H is connected
and does not contain any cycles. First note that H is connected by
definition of a connected component, so the first condition is satisfied. For the second condition, since F is a forest we know that F does not contain any cycles, and therefore as H is a subgraph of F it follows that H does not contain any cycles. Hence the second condition is
also satisfied and H is a tree.
Suppose that the graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic. Prove that G1 and G2 have the same degree sequence.
Since G1 and G2 are isomorphic, we know that there is a
bijective function f : V1 → V2 such that, for all u, v ∈ V1, we have
f(u)f(v) ∈ E2 if and only if uv ∈ E1. Since f is a bijection, it is sufficient to show that, for every vertex v ∈ V1, the degree of v in G1 is the same as the degree of f(v) in G2, since this would mean that the lists of degrees of vertices must be identical.
Fix an arbitrary vertex v ∈ V1. Since f is an isomorphism, we know
that for every u ∈ V1 \ {v}, f(u)f(v) is an edge in G2 if and only if
uv is an edge in G1. Thus the number of edges incident with v in G1 is the same as the number of edges incident with f(v) in G2, so the degree of v in G1 is the same as the degree of f(v) in G2.
Since this holds for any v ∈ V1, the result follows.
Let G be a graph, and suppose that there is a walk from u to v in G. Prove that G contains a path from u to v.
Let w1, . . . , wp be a walk from u to v in G, with p as small as possible. We claim that w1, . . . , wp is actually a path: if there is some 1 ≤ i < j ≤ p such that wi = wj
then w1, . . . , wi, wj+1, . . . , wp is a walk from u to v and is strictly shorter than w1, . . . , wp, so we would have chosen this instead. Therefore w1, . . . , wp is a path from u to v in G.
Suppose that every vertex in G has degree at least 2. Prove that G contains a cycle.
Suppose that G has n vertices. We begin by picking any starting
vertex v1 ∈ V(G), and choose v2 to be a neighbour of v1. Since v2
has degree at least 2, we can choose v3 to be a neighbour of v2 other than v1. Continuing in this way, for each i ≥ 2 choosing vi+1
to be a neighbour of vi other than vi−1, we obtain a sequence of vertices v1, v2, v3, . . .. We continue in this way until the first time we choose a vertex vj such that vj = vi for some i < j: this must happen eventually since the first n + 1 vertices we choose cannot all be distinct (there are only n vertices in total). Since this we have chosen the first such j, it follows that vi, vi+1, . . . , vj−1 are all distinct, and by construction we have vv+1 ∈ E(G) for i ≤ ` ≤ j − 2 and also vj−1vj = vj−1vi ∈ E(G), so vi, . . . , vj−1 is a cycle.
(Handshaking Lemma) Let G = (V, E) be a graph. Prove that
∑ d(v) = 2|E|
v∈V
We count the number of distinct pairs (v,e) where v ∈ V, e ∈ E and e is incident with v, in two different ways. First, note that
|{(v,e) : v ∈ V,e ∈ E, v incident with e}| = ∑ |{e ∈ E : v incident with e}|
v∈V
= ∑ d(v).
v∈V
On the other hand,
|{(v,e) : v ∈ V,e ∈ E, v incident with e}| = ∑ |{v ∈ V : v incident with e}|
e∈E
= ∑ 2
e∈E
= 2|E|.
Hence ∑ d(v) = 2|E|, as required.
v∈V
Let F be a forest on n vertices, with c connected components.
Then the number of edges in F is ___.
n − c.
Let G be a graph. Prove that G contains an even number of vertices whose degree is odd.
We will assume, for a contradiction, that the number of vertices of odd degree is odd. Let U be the set of vertices in G that have odd degree, and W the set of vertices that have even degree.
First observe that, since every vertex in W has even degree, ∑v∈W d(v) is even. Suppose now that U = {u1, u2, . . . , uk}, where k is odd. Then since the sum of any two odd numbers is even, so we see that
∑v∈U d(v) is odd.
Hence the sum of the degrees of all vertices is odd, but this contradicts the handshaking lemma.
Let G be a connected graph, and suppose that v ∈ V(G) with d(v) = 1. Prove that G’, the subgraph obtained from G by deleting v (and the one edge incident with v), is also connected.
Suppose, for a contradiction, that G’
is not connected. Then there exist two distinct vertices u, w ∈ V(G’) = V(G) \ {v} such that there is no path from u to w in G’. Since G is connected, there is a path u = x1, x2, . . . , xp = w in G. Since this path does not survive in G’, and we know that v is neither u nor w, we must have v = xi
for some 2 ≤ i ≤ p − 1. But each vertex
xi with 2 ≤ i ≤ p − 1 has at least two neighbours in G (xi−1 and xi+1), so d(v) ≥ 2. This contradicts the fact that d(v) = 1.
Hence G’ must be connected.
Prove that every tree on n ≥ 2 vertices contains at least one vertex of degree 1.
Suppose, for a contradiction, this is not the case, so there is some tree T on n ≥ 2 vertices which does not contain a vertex of degree one. If T contains a vertex of degree zero, then T is not connected, which is not possible as T is a tree. Therefore every vertex in T has degree at least 2. Then, by Theorem 3.4, we know that T contains a cycle, but this also contradicts the fact that T is a tree.
Therefore our initial assumption that T did not contain a vertex of degree one must have been false.
Let T be a tree on n vertices. Prove that T has n−1 edges.
We proceed by induction on n. The base case, for n = 1, is trivial, since the only graph with one vertex and no edges is a tree. This is our basis for the induction.
Given a tree with k vertices has k − 1 edges, we need to show a
tree with k + 1 vertices has k edges. Let Tk+1 be any tree with k + 1 vertices. Take any node v of Tk+1 of degree 1. Consider Tk , the subgraph of Tk+1 created by removing v and the edge connecting it to the rest of the graph. Tk is itself a tree and has k vertices and one less edge than Tk+1 by definition. By the inductive hypothesis, Tk has k − 1 edges therefore Tk+1 must have k edges and the result follows by the Principle of Mathematical
Induction.
Let G be a connected graph with n ≥ 1 vertices and n − 1 edges. Prove that G is a tree.
We proceed by induction on n. As before the base case, for n = 1, is trivial, since the only graph with one vertex and no edges is a tree.
Now assume that the theorem holds for every graph on at most k vertices. Let G be a connected graph with k + 1 vertices and k edges; we need to show that G has no cycles. Since G is a connected graph
with k + 1 ≥ 2 vertices, G has no isolated vertices, so the minimum degree of G is at least 1. If every vertex in G has degree at least 2, then
∑v∈V(G) d(v) ≥ 2|V(G)| = 2(k + 1) > 2k = 2|E(G)|, contradicting the fact that ∑v∈V(G) d(v) = 2|E(G)| for any graph G (Lemma 3.5).
So there is some vertex v ∈ V(G) with d(v) = 1.
Let G’ be the graph obtained from G by deleting v and the one edge incident with v. By Lemma 3.8, G’ is connected; moreover, as we have deleted exactly one vertex and one edge, G’ has k vertices and
k − 1 edges. It therefore follows from inductive hypothesis that G’ is a tree, so G’
contains no cycles. Thus any cycle in G must involve v. But v has degree 1, and every vertex in a cycle has degree at least 2, so v cannot belong to any cycles. Hence G contains no cycles, and is a tree.
Let G be a connected graph. Prove that G contains a spanning tree.
We proceed by induction on the number of cycles in G. If G contains no cycles then G is a tree, so G is a spanning tree for itself and we are done.
Now suppose that the result holds for any connected graph having at most k cycles, and let G be a connected graph with k + 1 ≥ 1 cycles. Let v1, . . . , v be a cycle in G, and let G' be the subgraph of G obtained
by deleting the edge vv1: we claim that G’ is connected. To check this, let u, w ∈ V(G’). We know that there exists a path P from u to w in G. If P does not include the edge vv1, then P survives in G'; otherwise we can replace the edge v1v with the path v1, v2, . . . , v` to obtain a walk from u to w and hence (by Lemma 3.3) a path from u to w. So G’
is connected, and it is also clear that G’ contains strictly fewer cycles than G.
Hence we can apply the inductive hypothesis to see that there exists a spanning tree T for G’. Since G’
is a spanning subgraph of G, T must also be a spanning tree for G, as required.
