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
- 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
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:
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.