Difference between revisions of "Tree (graph theory)"
Scrabbler94 (talk | contribs) |
(tag as stub; add fact) |
||
| Line 1: | Line 1: | ||
| − | A '''tree''' is an undirected [[Graph (graph theory)|graph]] which is both connected and acyclic. Equivalently, a tree is a graph <math>G=(V,E)</math> such that for any two vertices <math>u, v \in V</math> with <math>u \neq v</math>, there is exactly one path connecting <math>u</math> and <math>v</math> in <math>G</math>. Every tree | + | A '''tree''' is an undirected [[Graph (graph theory)|graph]] which is both connected and acyclic. Equivalently, a tree is a graph <math>G=(V,E)</math> such that for any two vertices <math>u, v \in V</math> with <math>u \neq v</math>, there is exactly one path connecting <math>u</math> and <math>v</math> in <math>G</math>. Every tree that has <math>|V|=n</math> vertices has exactly <math>n-1</math> edges. |
| + | |||
| + | The converse is also true: an undirected and connected graph with <math>n</math> vertices and <math>n-1</math> edges is a tree. | ||
| + | |||
| + | {{stub}} | ||
Revision as of 21:15, 4 July 2024
A tree is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph 
such that for any two vertices 
with 
, there is exactly one path connecting 
and 
in 
. Every tree that has 
vertices has exactly 
edges.
The converse is also true: an undirected and connected graph with 
vertices and edges is a tree.
This article is a stub. Help us out by expanding it.
