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.



Answers 2


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.

angryavian
angryavian
October 20, 2019 05:25 AM

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?

friedvir
friedvir
October 20, 2019 05:30 AM

Related Questions




5-color Theorem proof

Updated September 06, 2017 04:20 AM