Question

How do you prove that there must be at least one cycle in any graph with n vertices?

Answer 1

The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge). All the back edges which DFS skips over are part of cycles.