2
$\begingroup$

I am working on the following problem in my Topology class. While I do have an idea of how this proof should work I am having a hard time making into a nice proof. Here is the question and my attempt

A finite graph is called a tree if it is nonempty, connected and contains no cycles. Use the fact that a finite graph with no cycles contains a vertex with $\leq 1$ edges.

Attempt:

Since our graph is nonempty there exists at least one vertex. Let this vertex be a point in a tree such that it has $\leq1$. Then we know this vertex has either 0 edges extending from it or 1 edge extending from it.

case 1. this vertex has 0 edges extending from it. This gives us the single vertex so we have $n=0$ edges and $n+1$ vertices.

case 2. this vertex has one edge extending from it. In this case the edge must end a point that is not the original vertex (no cycles). Thus, we have a single edge connected by 2 vertices. We may also see that for any edge added to a vertex on this tree we must have a new endpoint (again there are no cycles). So, for every edge added there is also a vertex added. Continue adding edges and vertices to obtain our tree. Thus, for $n$ edges we have $n+1$ vertices.

$\endgroup$
  • $\begingroup$ I just fixed a few confusing typos. Hope that is ok. $\endgroup$ – almagest May 7 '16 at 7:37
  • 1
    $\begingroup$ A good start. In case 1 you need to explain why $n=0$ (answer the graph is connected). In case 2, your argument is somewhat unclear. It might be easier to try removing the vertex with a single edge and use induction. $\endgroup$ – almagest May 7 '16 at 7:41
  • $\begingroup$ Also have a look at this question and its answers $\endgroup$ – drhab May 7 '16 at 8:23
  • $\begingroup$ I don't understand what you're trying to do. I know that a tree with $n$ edges has $n+1$ vertices, but that's not what you're saying. What is "the tree of" a connected finite graph?? Your title says that, if you have a connected nonempty finite graph—let's call if $G$—and if $G$ has $n$ edges, then the "tree" of $G$ (whatever that is) has $n+1$ vertices. All right, let $G=K_5,$ that's a connected finite graph. It has $10$ edges, so according to you its tree has $11$ vertices. So whatever tree you're talking about can't be a subgraph of $G,$ which has only $5$ vertices. $\endgroup$ – bof May 7 '16 at 8:40
2
$\begingroup$

Perhaps a cleaner way of presenting your argument is as follows: we'll build your graph vertex-by-vertex.

So pick a vertex somewhere in your tree, since it's non-empty. This gives us 1 vertex and no edges, as we'd hope! Call this $\Gamma_1$, and call your tree $T$.

Now suppose we've already got $\Gamma_n$, a connected, non-empty finite graph with $n$ vertices and $n-1$ edges. If $\Gamma_n$ is all of $T$, then we're done. If not, then there's some vertices or edges in $T$ we haven't added to $\Gamma_n$ yet.

We should never reach the case where there are only edges missing, because $T$ has no cycles ($\Gamma_n$ is itself a tree, so if we add another edge between two of its vertices then we've made a cycle). So we can focus on just the case where there are more vertices to add.

There must be a vertex that has an edge joining it to $\Gamma_n$, since $T$ is connected. So add this vertex and this edge to $\Gamma_n$ to form $\Gamma_{n+1}$, which has $n+1$ vertices and $n$ edges.

Since $T$ is finite, this will eventually terminate, with $\Gamma_n$ being all of $T$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.