Tree

From Graph
Jump to: navigation, search
This article defines a property that can be evaluated to true/false for any undirected graph, and is invariant under graph isomorphism. Note that the term "undirected graph" as used here does not allow for loops or parallel edges, so there can be at most one edge between two distinct vertices, the edge is completely described by the vertices it joins, and there can be no edge from a vertex to itself.
View other such properties

Definition

An undirected graph with at least one vertex is termed a tree if it satisfies the following equivalent conditions:

  1. It is a connected graph and the subgraph obtained by deleting any edge from it (while keeping all vertices) is not connected.
  2. It is a connected graph that is also a forest: it has no cycles.
  3. (If the number of vertices is finite): It is a connected graph and the number of edges in it is one less than the number of vertices.