**Problem1C: Show that a connected graph on **** vertices is a tree if and only if it has **** edges.**

**Solution: **

** Only if: **First, we show that there exists a vertex of degree in a tree on vertices. Otherwise, suppose for any vertex 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 Suppose the conclusion is true for For a connected graph on vertices, if the graph is a tree, delete one vertex with degree together with its incident edge, then the remaining is a connected graph on vertices, and hence there are edges. So the conclusion is also true for The induction completes.

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

### Like this:

Like Loading...

*Related*