a graph with n node and n edges will have at least one cycle

Question

I am a student and my teacher gives us a question can you prove it for me please I cannot figure it out! a graph with n node and n edges will have at least one cycle and the condition of n is n>=3

Answer 1

The easiest proof I can think of without using any fancy lemmas and stuff goes as follows: Assume towards contradiction that there does exist a graph with n nodes and n edges that does not contain a cycle. Then, we can pick any start node and move to one of its neighbors via an edge. We can assume that without loss of generality every node has at least one incident edge via pigeonhole principle (n nodes, n edges), therefore every node has at least one neighbor. Since we moved to a neighboring node from our start node via one edge we have now connected two nodes but only used one edge. We can move to a neighbor of one of the visited nodes by another incident edge or visit a new node and move to its neighbor (thus also connecting two nodes but using only one edge) and inductively continue this process until we have visited all n nodes of the graph. It is trivial to see that we will only have used at max n - 1 edges (by fence-post lemma if you will). But since the graph has n edges there must exist another edge which we have not used. The only possibility for such an edge to exist is if it connects to a node that has already been visited. Therefore this n-th edge must complete a cycle and therefore the graph is cyclic. We have thus reached a contradiction with our root assumption and hence the graph must be cyclic.