We now consider undirected graphs. Recall that such a graph is • connected i for

Question

We now consider undirected graphs. Recall that such a graph is

• connected i for all pairs of nodes u, w, there is a path of edges between u and w;

• acyclic i for all pairs of nodes u, w, whenever there is an edge between u and w then there is no path

Given an acyclic undirected graph G with n nodes (where n 1) and a edges, your task is to prove that a n 1, and that equality holds (a = n 1) if and only if G is connected.
Hint: a possible approach is to do induction in a; for the case with a > 0, consider an edge {x, y} and partition G into 3 parts: the nodes connected to x (but not through that edge), those connected to y (but not through that edge), and the remaining nodes. Then apply the induction hypothesis to each part.

Explanation / Answer

Proof: Let T be an arbitrary tree. Assume that in any proper subtree of T, the number of vertices is one more than the number of edges. There are two cases to consider: Either T has one vertex, or T has more than one vertex. • If T has one vertex, then it has no edges. • Suppose T has more than one vertex. Because T is connected, every pair of vertices is joined by a path. Thus, T must contain at least one edge. Let e be an arbitrary edge of T, and consider the graph T obtained by deleting e from T. Because T is acyclic, there is no path in T e between the endpoints of e. Thus, T has at least two connected components. On the other hand, because T is connected, T e has at most two connected components. Thus, T e has exactly two connected components; call them A and B. Because T is acyclic, subgraphs A and B are also acyclic. Thus, A and B are subtrees of T, and therefore the induction hypothesis implies that |E(A)| = |V(A)| 1 and |E(B)| = |V(B)| 1. Because A and B do not share any vertices or edges, we have |V(T)| = |V(A)| + |V(B)| and |E(T)| = |E(A)| + |E(B)| + 1. Simple algebra now implies that |E(T)| = |V(T)| 1. In both cases, we conclude that the number of vertices in T is one more than the n

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.