[그래프이론(Graph Theory) 문제풀이] Deleting a vertex of degree δ(G) cannot reduce the average degree.

그래프이론(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가 됩니다.

참고할만한 글:

문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 3 문제

Leave a Comment