Proving that "every acyclic, connected graph with V vertices has V-1 edges"

by mindcrime   Last Updated October 20, 2019 05:20 AM - source

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.



Related Questions




5-color Theorem proof

Updated September 06, 2017 04:20 AM