그래프이론(Grpah Theory)문제풀이 해보겠습니다. 이번에 풀어보고자 하는 문제는 아래와 같습니다.
Prove or Disprove: Deleting a vertex of degree δ(G) cannot reduce the average degree.
minimum degree를 갖는 vertex를 제거하면 average degree가 증가하는지를 묻고 있습니다. 이 글을 읽으시면 이해가 되실 겁니다.
그래프이론(Graph Theory) 문제 풀이 방법
아래와 같은 문제를 풀기로 하였습니다.
Prove or Disprove: Deleting a vertex of degree δ(G) cannot reduce the average degree.
이런 문제는 증명을 하던가 성립하지 않는 예시를 보인다면 풀립니다. 저는 성립하지 않는 예시를 들겠습니다. Complete graph K_3 가 있다고 합시다. 그러면 \delta(K_3)=2 이고 average degree는 2입니다. 여기서 아무 vertex를 제거 합니다. 그렇게 된다면 그래프는 K_2 가 되고 average degree를 1가 됩니다.
참고할만한 글:
- [그래프이론(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
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 3 문제