Graph Theory/Trees
Jump to navigation
Jump to search
A tree is a type of connected graph. An directed graph is a tree if it is connected, has no cycles and all vertices have at most one parent. An undirected graph is considered a tree if it is connected, has edges and is acyclic (a graph that satisfies any two of these properties satisfies all three).
Exercise: Equivalent Definitions
Show that the following are equivalent definitions for a tree:
Hint: To keep the total proof short, put the definitions in a suitable order, and then prove A=>B=>C=>D=>E=>A. Take particular care over graphs with zero and one node.

This section is a stub. You can help Wikibooks by expanding it. 
Acyclic and connected .
is acyclic graph. So,
 Meaning
 tree : minimum connected graph
 cycle : minimum 2connected graph