[그래프이론(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.

by

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





그래프이론(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.

n개의 vertex 를 가지는 graph 의 maximum degree 가 ⌈n/2⌉ 이고 minimum degree가 ⌊n/2⌋ − 1 일 때 G가 connected임을 보이는 문제입니다. 여기서 ⌈⌉ 와 ⌊⌋에 대해서는 이 글을 보시는 것을 추천 드립니다. 어떻게 하면 풀 수 있을까요? maximum degree를 갖는 vertex u와 minimum degree를 vertex v를 이용하면 됩니다. maximum degree가 ⌈n/2⌉ 이므로 vertex u 를 포함하는 component Cu의 원소의 갯수는 |Cv| = ⌈n/2⌉+1 이상입니다. 그리고 minimum degree 가 ⌊n/2⌋ − 1 이므로 v를 포함하는 component Cv의 원소의 갯수는 |Cv|=⌊n/2⌋ 이상입니다. 만약에 Cu와 Cv가 disjoint 하다면 |V(G)| ≥|Cu|+|Cv| ≥⌈n/2⌉+⌊n/2⌋+1>n=|V(G)| 이 되므로 Cu와 Cv는 intersection 이 있습니다. 따라서 Cu와 Cv는 갖습니다. 비슷한 논리로 임의의 vertex w에 대하여 Cu=Cw 입니다. 따라서 Component가 하나만 존재합니다. 그러므로 G는 connected 입니다.

참고할만한 글:

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

3 thoughts on “[그래프이론(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.”

  1. 안녕하세요.

    비슷한 논리로 임의의 vertex w에 대하여 Cu=Cw 입니다.

    이 부분이 잘 이해 안 가는데, Cw는 Cv와 달리 order에 대한 정보가 제공되지 않는데 앞에서 보인 것과 비슷한 논리를 사용한다는 게 어떤 의미인지 잘 모르겠어서요. 혹시 자세한 설명 가능할까요?

    감사합니다.

    응답

Leave a Comment