Graph Theory
Jump to navigation
Jump to search
Trees
For an unconnected graph G, the following are equivalent
- G is connected and acyclic (contains no cycles).
- G is acyclic, and a simple cycle is formed if any edge is added to G.
- G is connected, but would become disconnected if any single edge is removed from G.
- G is connected and the 3-vertex complete graph K3 is not a minor of G.
- Any two vertices in G can be connected by a unique simple path.