Vipul: Created page with "{{undirected graph property}} ==Definition== An undirected graph is termed a '''forest''' or '''acyclic graph''' if it satisfies the following equivalent conditions: # ..."

2012-05-28T18:09:59Z

Created page with "{{undirected graph property}} ==Definition== An undirected graph is termed a '''forest''' or '''acyclic graph''' if it satisfies the following equivalent conditions: # ..."

New page

{{undirected graph property}}

==Definition==

An [[undirected graph]] is termed a '''forest''' or '''acyclic graph''' if it satisfies the following equivalent conditions:

# It has no [[subgraph]] isomorphic to a [[defining ingredient::cycle graph]] of size three or more
# All its connected components are [[defining ingredient::tree]]s, i.e., it is a vertex-disjoint union of trees
# Its [[defining ingredient::girth of a graph|girth]] is <math>\infty</math>

==Relation with other properties==

===Stronger properties===

{| class="sortable" border="1"
! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
|-
| [[Weaker than::tree]] || || || ||
|}

===Weaker properties===

{| class="sortable" border="1"
! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
|-
| [[Stronger than::triangle-free graph]] || || || ||
|}

Forest - Revision history

Vipul: Created page with "{{undirected graph property}} ==Definition== An undirected graph is termed a '''forest''' or '''acyclic graph''' if it satisfies the following equivalent conditions: # ..."