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:

- 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.
- But at least one vertex is the other side of a vertex pair, so subtract "its edge". That leaves V-1 edges.
- The graph is connected by definition in the problem so there is now a path from any vertex to any other
- 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.

- Serverfault Help
- Superuser Help
- Ubuntu Help
- Webapps Help
- Webmasters Help
- Programmers Help
- Dba Help
- Drupal Help
- Wordpress Help
- Magento Help
- Joomla Help
- Android Help
- Apple Help
- Game Help
- Gaming Help
- Blender Help
- Ux Help
- Cooking Help
- Photo Help
- Stats Help
- Math Help
- Diy Help
- Gis Help
- Tex Help
- Meta Help
- Electronics Help
- Stackoverflow Help
- Bitcoin Help
- Ethereum Help