그래프이론 (Graph Theory) 문제풀이 글 입니다. 이번에 풀어볼 문제는 “Prove or disprove: Every tree T has at least ∆(T) leaves.”입니다. 이것을 어떻게 풀까요?
그래프이론 (Graph Theory) 문제풀이
이번에 풀어볼 문제를 다시 정리하면 아래와 같습니다.
Prove or disprove: Every tree T has at least ∆(T) leaves.
어떤 Tree이건 이것의 maximum degree이상의 leaf를 갖는가를 묻는 문제입니다. 문제풀이 해보겠습니다. maximum degree를 M이라 표시할 게요. v를 maximum degree를 갖는 T의 vertex라고 합시다. 그랬을 때 v 의 neighbors는 M개가 있습니다. 이 M개의 vertex는 leaf이던가 leaf가 아니면 쭉쭉 타고가서 leaf를 한개 이상 만듭니다. 즉 어쨋든 M개 이상의 leaf를 만든다는 뜻입니다. 따라서 Tree T는 최소 M개 이상의 leaf를 갖는다.
참고할만한 글:
- [그래프이론(Graph Theory)] Deleting a vertex of degree ∆(G) cannot increase the average degree.
- [그래프이론(Graph Theory) 문제풀이] Prove or disprove: K9 decomposes into copies of C9.
- [그래프이론(Graph Theory)] Use induction to prove that if a graph does not have an odd cycle then it is bipartite.
- [그래프이론(Grpah Theory)] Prove that the Petersen graph has no cycle of length 7.
- [그래프이론(Graph Theory) 문제풀이] Find all simple graphs with n vertices having no isolated vertex and no induced subgraph with exactly two edges.
- [그래프이론(Graph Theory) 문제풀이]Let P and Q be be paths of maximum length in a connected graph G. Prove that P and Q have a common vertex.
- [그래프이론 문제풀이] Let u and v be adjacent vertices in a simple graph G. Prove that uv belongs to at least d(u) + d(v) − n(G) triangles in G.
- [그래프 이론(Graph Theory)-1] k-set과 k-subset
- [그래프이론(Graph Theory) 문제풀이] Deleting a vertex of degree δ(G) cannot reduce the average degree.
- [그래프이론(Graph Theory)] 문제 풀이 Prove or disprove: If G is an n-vertex simple graph with maximum degree ⌈n/2⌉ and minimum degree ⌊n/2⌋ − 1, then G is connected.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 3 문제