728x90
반응형
문제출처
광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5
Solution
1. Consider an edge e∈E(T)−E(T′). Since e is not in T′, adding e to T′ results in the graph T′+e.
- Because T′ is a spanning tree, it already spans all vertices of G.
- This means there is a path in T′ between any two vertices. Adding e, which is incident to two vertices already connected by a path in T′, must create a cycle in T′+e. Let this cycle be C.
2. Since C is a cycle in the graph T′+e, it contains at least two distinct paths between the vertices incident to e.
- These paths consist of edges from T′, because T′ spans the entire vertex set of G.
- As e∈E(T) and e∉E(T′), the cycle C must contain at least one edge from T′ that is not in T.
- This edge is denoted by e′∈E(T′)−E(T), and it lies on C.
3. Now consider the graph T′+e−e′.
- By deleting e′ from C, the cycle is destroyed, and the resulting graph T′+e−e′ is acyclic.
- Since T′+e−e′ still spans all vertices of G, because neither e nor e′ disconnects any vertex, it remains connected and contains n−1 edges.
- Therefore, T′+e−e′ is a spanning tree of G.
4. Next, consider the graph T−e+e′.
- Deleting the edge e from T breaks the tree structure and may disconnect the graph, leaving it no longer a tree.
- However, adding the edge e′∈E(T′)−E(T) reconnects the graph because e′ lies on the cycle C, which connects vertices that were possibly disconnected by removing e.
- Since the graph T−e+e′ now has n−1 edges and remains connected, it must be a tree.
- Additionally, because no cycles were introduced by this operation, T−e+e′ is acyclic.
- Thus, T−e+e′ is a spanning tree of G.
728x90
반응형