DM-ProblemSet4-Sols[pelo menos k leaves]

Prévia do material em texto

Discrete Mathematics 2013 – Problem Set 4 – Solutions
1. Prove that every tree with a vertex of degree k has at least k leaves.
Solution. We may assume that k ≥ 2, as the statement for k = 1 is trivial. Let x
denote the number of vertices of degree 1 (leaves) and n denote the number of all
vertices. Hence there are n−x vertices of degree at least 2, one of which has degree k.
Since the sum of all vertex degrees is 2n− 2, we have x + 2(n− x− 1) + k ≤ 2n− 2.
This implies x ≥ k.
2. Prove that every acyclic graph with n vertices and n− 1 edges is a tree.
Solution 1. Let G be a graph with n vertices. Let G1, . . . , Gk denote the connected
components of G, that is, the maximum (in the sense of the subgraph relation) con-
nected subgraphs of G. Let ni denote the number of vertices of Gi. Clearly, each Gi
is itself acyclic, so it is a tree and thus has ni − 1 edges. Hence the total number of
edges in G is
∑k
i=1(ni − 1) = n − k. Consequently, if G has n − 1 edges, then k = 1,
which means that G is connected and thus is a tree.
Solution 2. It is enough to prove the following statement: every acyclic graph with n
vertices and n − 1 edges is connected. The proof goes by induction on n. The basic
case n = 1 is trivial. Thus assume n ≥ 2. Let G be an acyclic graph with n vertices
and n − 1 edges. The sum of all vertex degrees in G is 2n − 2, so there is a vertex v
in G with degree 0 or 1.
Suppose degG(v) = 1. Let G
′ denote the graph obtained from G by removing the
vertex v and the edge connecting v to its only neighbor. The graph G′ is acyclic and
has n − 1 vertices and n − 2 edges, so by the induction hypothesis it is connected.
Hence G is connected as well.
Now, suppose degG(v) = 0. Let G
′ denote the graph obtained from G by removing
the vertex v and an arbitrarily chosen edge xy. The graph G′ is acyclic and has n− 1
vertices and n − 2 edges, so by the induction hypothesis it is connected. Hence G′
contains a path from x to y. This path cannot consist of the single edge xy only,
because xy is not in G′. Therefore, this path together with the edge xy forms a cycle
in G, which is a contradiction.
3. Recall that a path from a vertex u to a vertex v in a graph is a sequence (x0, x1, . . . , xk)
of vertices such that x0 = u, xk = v, and xixi+1 is an edge for 0 ≤ i ≤ k − 1. Prove
that a graph is a tree if and only if for any two vertices u and v there exists exactly
one path from u to v.
Solution. Let G be a graph with the property that for any two vertices u and v there
exists exactly one path from u to v. Since any two vertices u and v are connected
by a path, the graph G is connected. If there is a cycle (x1, x2, . . . , xk) in G, then
(x1, x2, . . . , xk) and (x1, xk) are two different paths connecting vertices x1 and xk, which
cannot exist. Therefore, the graph G is acyclic.
Now, let G be a tree, and suppose there are two paths (x0, x1, . . . , xk) and (y0, y1, . . . , y`)
between two vertices x0 = y0 = u and xk = y` = v. Let r be the greatest index
such that (x0, x1, . . . , xr) = (y0, y1, . . . , yr) and s be the least index in {r + 1, r +
2, . . . , k} such that xs = yt for some t ∈ {r + 1, r + 2, . . . , `}. It follows that the
vertices xr+1, xr+2, . . . , xs−1 and yr+1, yr+2, . . . , yt−1 are pairwise distinct. Therefore,
(xr, xr+1, . . . , xs−1, xs = yt, yt−1, . . . , yr+1) is a cycle in G, which is a contradiction.
1
4. Consider an n-vertex complete graph with a selected edge e. Prove that the graph
contains 2nn−3 spanning trees containing the edge e.
Solution. Let G be an n-vertex complete graph. For any edge e of G, let xe denote the
number of spanning trees containing the edge e. All the numbers xe are equal, because
G is symmetric with respect to any permutation of its vertices. Let x denote the
common value of all xe. We count the total number of edges in all spanning trees of G
in two ways. On the one hand, it is (n−1)nn−2, as there are nn−2 spanning trees, each
with n− 1 edges. On the other hand, this number is ∑e∈E xe = (n2)x = n(n− 1)x/2.
Comparing the two, we obtain x = 2nn−3.
5. Consider a directed graph G whose vertices are sequences (x1, x2, . . . , xk−1) of zeros
and ones of length k − 1 and whose edges are defined so that for any x1, x2, . . . , xk ∈
{0, 1} there is a directed edge from (x1, x2, . . . , xk−1) to (x2, . . . , xk−1, xk). Prove that
the graph G is Eulerian. Using an Euler tour in this graph, construct a sequence
(x1, x2, . . . , xn) of zeros and ones of length n = 2
k + k− 1 with no two identical blocks
of size k, that is, with no two identical subsequences of the form (xi, xi+1, . . . , xi+k−1)
for 1 ≤ i ≤ n− 1.
Solution. The graph G has 2k−1 vertices and 2k edges. To show that G is Eulerian,
we use the characterization provided by Problem 4 in Problem Set 3. Between any
two vertices (x1, x2, . . . , xk−1) and (xk, xk+1, . . . , x2k−2), there is a path in G going
through vertices (xi, xi+1, . . . , xi+k−2) for 1 ≤ i ≤ k. Thus G is weakly connected.
Moreover, every vertex of G has in-degree and out-degree equal to 2. Using the char-
acterization, we conclude that G is Eulerian. An Euler tour in G goes through vertices
(xi, xi+1, . . . , xi+k−2) for 1 ≤ i ≤ 2k + 1 and a sequence (x1, x2, . . . , x2k+k−1) of zeros
and ones. Since every edge of G occurs in the Euler tour exactly once, every block
(xi, xi+1, . . . , xi+k−1) occurs in the sequence exactly once.
2