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 connected components with edges and vertices then .
Now it is pretty obvious that if then there must exist a cycle.