View source for Graph Theory


==Trees==
{{main | Wikipedia:Tree (graph theory)}}
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.