[그래프이론 (Graph Theory) 문제풀이] Present the proof we learned in class using 2-switch method to show that there is a simple graph with degree sequence d = 432222111 from the following simple graph G with degree sequence d = 6543333111. Start with G − v .

그래프이론 (Graph Theory) 문제풀이를 해보겠다. 이번에 풀 문제는 “Present the proof we learned in class using 2-switch method to show that there is a simple graph with degree sequence d’ = 432222111 from the following simple graph G with degree sequence d = 6543333111. Start with G − v.” 이다.

그래프이론 (Graph Theory) 문제풀이

이번에 풀 문제를 다시 Remind 해보겠습니다.

Present the proof we learned in class using 2-switch method to show that there is a simple graph with degree sequence d’ = 432222111 from the following simple graph G with degree sequence d = 6543333111. Start with G − v.

위와 같이 degree sequence 가 d=6543333111 인 graph 가 있을 때 2-switch method 를 이용해서 degree sequnce가 d’=432222111인 graph 를 만들라는 얘기이다.
풀이) degree sequence d=6543333111중 최대값 6에 대응되는 vertex v 를 Pick하자.
그리고 v와 adjacent 한 vertex의 degree를 확인해보니, 433111이다.
문제를 다시생각해보면 d=6543333111 에서 6에 해당되는 vertex를 제거함으로써 d’=432222111인 sequence를 만들려고 한다.
그러기 위해서는 degree가 6인 vertex의 adjacent 한 vertex의 degree가 각각 543333이면, v를 제거했을 때 자동적으로 degree sequence가 d’=432222111인 graph 가 만들어진다.
그렇다는 것은 vertex v와 adjacent한 vertices 들의 degree를 543333이 되도록 만들어주면 된다는 얘기이다.
이 때 쓰이는 방법이 2-switch method 이다.
아래와 같은 방식으로 2-switch를 행한 후 vertex v를 버리면 원하는 그래프가 만들어진다.

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