1
$\begingroup$

I'm self-studying Robert Sedgewick's book Algorithms in Java: Part 5 - Graph Algorithms (3rd ed), and am looking for a sanity check (and possibly some help) on Exercise 17.1. The exercise asks:

Prove that any acyclic, connected graph with V vertices has V-1 edges.

Superficially this seems to follow so directly from the definitions / conditions stated earlier in the chapter, that I'm not sure what a "proof" would even constitute here (if I were doing this in a class).

The definitions tell us:

  • An acyclic, connected graph is called a tree

and

  • A graph G with V vertices is a tree iff any of the following:
    • G has V-1 edges and is acyclic
    • G has V-1 edges and is connected
    • snip

Any one of these conditions is necessary and sufficient to prove the others

Given that, it seems almost to be "by definition" that an acyclic, connected graph with V vertices has V-1 edges.

I suspect that something more is really being sought here, and the best I've come up with so far is something like this:

  1. For a connected, acyclic graph with V vertices, each vertex needs one edge to even be part of the graph at all. This would appear to leave us needing V edges.
  2. But at least one vertex is the other side of a vertex pair, so subtract "its edge". That leaves V-1 edges.
  3. The graph is connected by definition in the problem so there is now a path from any vertex to any other
  4. Adding any additional edge now would create a cycle since the graph is already connected

Thoughts? Am I going about this all wrong? If so, any pointers or hints would be appreciated. Note: I don't have a background in writing proofs, so please be gentle. I have a vague notion that the major proof strategies are "deductive proof" following from definitions, "proof by contradiction" and "proof by induction" but I'm pretty inexperienced here, especially with the latter two approaches.

$\endgroup$
1
$\begingroup$

well, you are on the right path. basically, what you need to do in those kind of questions is or using induction, or assuming by contradiction that the claim isn't right (lets say, $G$ it's a acyclic, connected graph with $V$ vertices and less or more then $|E|=|V|-1$ edges, and then disprove that.

for example: lets us assume that $G$ it's a acyclic, connected graph with $V$ vertices and has less then $|E|=|V|-1$ edges. according to 'Pigeonhole principle', at least one vertex $v\in V$ has a degree of $0$ and therfore the graph isn't connected. now, lets us assume that $G$ it's a acyclic, connected graph with $V$ vertices and has more then $|E|=|V|-1$ edges. can you get it from here?

$\endgroup$
1
  • $\begingroup$ Thanks, I'll pick this up again tomorrow after digesting the answers here ,and sleeping on it. Hopefully it will make more sense then. $\endgroup$ – mindcrime Oct 20 '19 at 5:44
1
$\begingroup$

You are given a definition: "an acyclic, connected graph is called a tree."

You are then presented with a claim that this definition is equivalent to "has $V-1$ edges and is acyclic" and also equivalent to "has $V-1$ edges and is connected." This claim is not proved in the text, and indeed the purpose of the exercise is to prove part of this claim. Thus you may not use the claim when doing the exercise, and must rely on only the initial definition of tree that you were given.


The usual approach is induction on $V$. If $V = 1$, then obviously the claim holds.

Now suppose we have proven the claim for $V = n$. We consider an acyclic connected graph with $n+1$ vertices and seek to show it has $n$ edges. Such a graph must have a leaf (vertex of degree $1$). Deleting that vertex and its accompanying edge will produce a graph that is also acyclic and connected. By the inductive hypothesis, this smaller graph has $n-1$ edges, so the original graph has $n$ edges.

$\endgroup$
3
  • $\begingroup$ Awesome, thanks for the help. I had earlier thought that this might be a place where proof by induction would come into play, but I'm so new to proofs that I couldn't convince myself that was the right path. $\endgroup$ – mindcrime Oct 20 '19 at 5:43
  • $\begingroup$ OK, I think I see how your inductive approach works, as you're starting from V=n and removing edges. Wouldn't it work just as well to start from V=1 (where E=0) and show that adding any vertex that yields a connected, acyclic graph entails adding exactly 1 edge, so the induction is basically building up from E=0 to E=V-1 as you add edges (instead of removing them)? $\endgroup$ – mindcrime Oct 20 '19 at 21:56
  • $\begingroup$ @mindcrime If you want to do it that way, you must show that any acyclic connected graph can be built up from a sequence of acyclic connected graphs by adding vertices one by one. But proving this would amount to going backward (deleting vertices) anyway. $\endgroup$ – angryavian Oct 21 '19 at 2:46

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.