# Thread: Cycle in Graph Theory.

1. ## Cycle in Graph Theory.

G = (V,E) has m edges and n vertices.
Proof that if m >= n, G has a cycle.

2. Originally Posted by le_su14
G = (V,E) has m edges and n vertices.
Proof that if m >= n, G has a cycle.
Definition: A connected graph that contains no cycles is called a TREE.

Theorem: (This is a theorem that I assume you know). Given a graph that is a tree the # of edges is 1 less the # of vertices.

Now given any (finite) graph we can break it up into connected peices. Those peices are called CONNECTED COMPONENTS. So for example an ordinary tree has 1 connected components.

Definition: A graph where each connected component is a tree is called a FOREST.

Using the theorem that was mentioned try to prove the following stronger result. Given a graph with $\displaystyle c$ connected components with $\displaystyle e$ edges and $\displaystyle v$ vertices then $\displaystyle e = v - c$.

Now it is pretty obvious that if $\displaystyle e\geq v$ then there must exist a cycle.