Problem1C

Problem1C: Show that a connected graph on {n} vertices is a tree if and only if it has {n-1} edges.

Solution:

Only if: First, we show that there exists a vertex of degree {1} in a tree on {n} vertices. Otherwise, suppose {\deg (v)\geq 2} for any vertex {v.} In other words, there are at least two edges connected to a vertex. Then start a path from an arbitrary vertex, if we reach some ‘new’ vertex from one edge connected to it, we can always go out of that vertex by another edge. Since there are only finite number of new vertices, we will reach some ‘old’ vertex if we keep going. Thus a closed path exists, which is a contradiction to the definition of a tree. We observe that the conclusion is true for {n=1.} Suppose the conclusion is true for {n=k.} For a connected graph on {k+1} vertices, if the graph is a tree, delete one vertex with degree {1,} together with its incident edge, then the remaining is a connected graph on {k} vertices, and hence there are {k-1} edges. So the conclusion is also true for {n=k+1.} The induction completes.

If: Suppose a graph on {n} vertices is connected with {n-1} edges. If it contains a closed path of length {k,} to make all the other {n-k} vertices connect to this closed path, we need at least {n-k} more edges. Hence the graph contain at least {n} edges, which is a contradiction. Therefore, this connected graph contains no closed path, thus is a tree.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: