그래프이론(Graph Theory)문제를 풀어보도록 하겠습니다. 이번에 풀어볼 문제는 아래와 같습니다.
Deleting a vertex of degree ∆(G) cannot increase the average degree.
maximum degree를 갖는 vertex를 제거하면 average degree가 유지되거나 작아진다는 명제입니다. 한번 이문제 풀어보도록 할께요.
그래프이론(Graph Theory) 문제 풀이
문제를 다시 언급하도록 할게요.
Deleting a vertex of degree ∆(G) cannot increase the average degree.
이것을 어떻게 풀어야 할까요? 일단 \Delta(G) 의 크기가 어느정도인지 부터 보겠습니다. 그래프 G 의 average degree 는 \frac{2 e(G)}{ n(G)} 로 표현됩니다. 여기서 e(G) 는 그래프 G 가 가지고 있는 총 edge의 수입니다. 그리고 n(G) 는 그래프 G 가 가지고 있는 총 vertex 의 수입니다. 이 때 \Delta(G) 의 크기를 대강 가늠할 수 있습니다.
\Delta(G) \leq \frac{e(G)}{n(G)} 이라면 아래와 같이 모순이 발생합니다.
\begin{align*} \frac{2e(G)}{n(G)} & = \sum_{v \in V(G)} \frac{ deg_G(v) }{n(G)} \\ & \leq \sum_{v\in V(G)} \frac{ \Delta(G)}{n(G)} \\ &= \Delta(G) \\ & \leq \frac{ e(G)}{n(G)} \end{align*}그러므로 \Delta(G) > \frac{e(G)}{n(G)} 가 성립합니다. 이제 deg_G(v) = \Delta(G) 인 v 를 G 로부터 제거할 때 average degree 가 어떻게 변하는지 보겠습니다. H= G-v 라고 합시다. 그러면 H 의 average degree 는 아래와 같습니다.
\begin{align*} \frac{2e(H)}{n(H)} &= \frac{ 2 (e(G)- \Delta (G))}{n(G)-1} \\ &< \frac{ 2(e(G) - \frac{e(G)}{n(G)})}{n(G)-1}\\ & = \frac{2e(G)}{n(G)} \end{align*}따라서 Maximum degree를 갖는 vertex를 제거하면 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
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 3 문제