Search code examples
data-structuresgraphtreetheory

Connected undirected acyclic graphs versus trees

While I'm studying about graph theory with MIT book 'introduction to algorithm', I was referred to some definitions about graphs and trees.

In MIT's Introduction to Algorithm 3rd Edition book, the appendix tree chapter shows me Theorem B.2, "Properties of Free Trees"

Let G = (V,E) be an undirected graph. The following statements are equivalent.

  1. G is a free tree ...
  2. G is acyclic, and |E| = |V| - 1.

Is there an example of connected, undirected, acyclic graph which is not a tree?

Theoritically, if there is a undirected acyclic graph which satisfies the condition that |E| =! |V| - 1, would that work as an example?

If there is an example satisfies that condition, can you show me?

Solution

  • Any connected acyclic graph is a tree. There are several different equivalent definitions of trees:

    • They're connected acyclic graphs.
    • They're connected graphs with one more node than edge.
    • They're minimally-connected graphs (they're connected, but removing any edge disconnects them)
    • They're maximally acyclic graphs (they're acyclic, and adding any missing edge creates a cycle)
    • They're graphs where any two nodes have exactly one simple path between them.

    So no, you can't find a connected acyclic graph that isn't a tree. :-)