문제출처
광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5
Solution
1. Suppose that there is a graph with $n$ vertices and no edges.
2. As we add edges to the graph, we need to determine whether each new edge creates a cycle. A cycle is formed when there is already a path between the two vertices before the edge is added.
3. At the beginning, there are $n$ disconnected vertices. By adding $n-1$ edges, we can make all the vertices part of a single connected component without creating any cycles. This is because the resulting graph is a spanning tree, which by definition is acyclic and includes all vertices.
4. After forming the tree, any additional edge will necessarily create a cycle, since all vertices are already part of the same connected component, meaning there is already a path between any two vertices.
5. Any edges beyond these $n-1$ will create a cycle. Therefore, if the graph has $m$ edges, the minimum number of cycles in the graph is $m - (n-1)$.