Dirac's Theorem and its Generalization

Graph Theory (basic)

Graph Theory (basic)

이전 글에서 minimum degree와 cycle의 관계를 활용해서 증명들을 몇 개 했었다. 이 글에서도 minimum degree $\delta$와 cycle, 특히 Hamilton cycle과의 관계를 살펴볼 예정이다.

 

Hamilton Path, Hamilton Cycle, Hamiltonian Graph

Hamilton path는 그래프의 모든 vertex를 포함하는 path다.

Hamilton cycle은 그래프의 모든 vertex를 포함하는 cycle이다.

Hamiltonian graph는 Hamilton cycle을 포함하는 그래프이다.
(Hamilton path를 포함하는 그래프는 traceable graph라고 한다.)

그래프가 Hamilton cycle을 포함하는지 판별하는 문제는 NP-complete다.

Traveling Salesman Problem은 minimum weight Hamilton cycle을 찾는 문제다. (당연히 역시 NP-complete다.)

 

Dirac's Theorem은 Hamilton cycle이 존재한다는 것을 보장하기 위해서 minimum degree $\delta$가 얼마나 커야 하는지에 관한 정리다.

 

Dirac's Theorem

$n(\ge 3)$개의 vertices를 가진 simple graph의 minimum degree $\delta$가 $\delta \ge n/2$를 만족할 때,
그 그래프는 Hamilton cycle을 가진다.

 

Note. $n\ge 3$ 조건이 있어야 하는 이유는 그래프가 두개의 vertices와 이 둘을 이어주는 하나의 edge로 구성되어 있는 경우 때문이다. ($K_2$)

 

이 정리에 대한 3가지 증명을 소개할 것이다. 우선 모든 증명들에서 쓰이는 Lollipop Lemma를 소개하도록 하겠다. 

 

Definition. $(x,y)$-lollipop

$(x,y)$-lollipop은 $C\cap P=\{y\}$을 만족하는 cycle $C$와 $xy$-path $P$의 union, $C\cup P$이다. (Lollipop은 lasso나 loop라고도 불리기도 한다.)

$(x,y)$-lollipop

Notation. Successor $v^{+}$, Predecessor $v^{-}$

Orientation이 있는 cycle $C$위의 한 vertex를 $v$라고 하자. $C$위에서 $v$의 다음 vertex(successor)를 $v^{+}$로, 이전 vertex(predecessor)를 $v^{-}$로 부르겠다. 이 notation은 $C$의 vertices의 subset $S$로도 연장될 수 있다.

$$S^{+}:=\{v^{+}|v\in S\}$$ $$S^{-}:=\{v^{-}|v\in S\}$$

Successor and Predecessor of $v$

The Lollipop Lemma

$G$에서 cycle $C$의 길이 = $l$, path $P$의 길이 = $m$을 만족하는 $C\cup P$가 $(x,y)$-lollipop이라고 하자.
그러면 $G$는 길이가 $l+m-1$인 $x{y}^{-}$ path와 $x{y}^{+}$ path를 포함한다.
만약에 $C$가 $G$의 longest cycle이고 $m$이 0이 아니라면, $y$에서 $m$ 이하로 떨어진 $C$위의 vertex는 $x$와 adjacent할 수 없다.

 

두 번째 문장은 쉽게 이해가 된다. 사실 세 번째 문장도 그다지 어렵지 않다. $y$에서 거리가 $m$ 이하로 떨어진 $C$위의 vertices 집합을 $L$이라 하자. 만약 $x$가 $L$에 속한 vertex와 하나라도 adjacent했다면 길이가 더 긴 cycle이 있다는 말이기에 $C$가 longest cycle이라는 것과 모순이 생긴다.

(추가 설명)

$x$가 $L$에 속한 $c$와 adjacent했다고 가정하자. 그러면 기존의 cycle의 $\cdots -\{c-\cdots -y\}-\cdots$부분을 $\cdots -c-[x-\cdots -y]-\cdots$로 cycle을 더 늘릴 수 있다. { } 부분이 $m$보다 작거나 같은 $C$의 부분이고 [ ] 표시된 부분이 대체된 $P$ 부분이다. 길이가 최소 1 늘어난 것을 알 수 있다.

굉장히 간단하고 당연해 보이는 이 lemma난 Dirac's Theorem을 보이는 데 큰 역할을 한다.

 

Dirac's Theorem. $n(\ge 3)$개의 vertices를 가진 simple graph의 minimum degree $\delta$가 $\delta \ge n/2$를 만족할 때, 그 그래프는 Hamilton cycle을 가진다.

 

Proof 1. By choosing a longest cycle

$C$를 $G$에서 길이가 $l$인 longest cycle이라 하자. 우리는 $l\ge \delta +1$, 즉 $l>\delta$임을 알 수 있다. (이전 글의 2 참고, 길이가 최소 $\delta$인 path가 존재함을 이용한다.) 만약 $C$가 Hamilton cycle이면 증명할 것이 없다. 따라서 $C$가 Hamilton cycle이 아니라고 가정하자. (즉, $G\mathrm{\setminus }C\ne \mathrm{\varnothing }$라고 가정하자.)

$C\cup P$를 $(x,y)$-lollipop이라고 하자. 이때 $P$는 길게 잡을 수 있는 만큼 최대한 길게 설정한다. 이 $P$의 length를 $m$이라 하자. 그러면

$$\delta \ge n-\delta >n-l=|G\mathrm{\setminus }C|$$

을 만족한다. (첫 번째 부등식은 $\delta \ge n/2$ 조건에서 오고, 두 번째는 $l>\delta$에서 오고 마지막 등식은 $l$이 $C$의 크기이기 때문에 성립한다.)

위에서 구한 $\delta >|G\mathrm{\setminus }C|$의 의미를 살펴보자. $G\mathrm{\setminus }C$의 크기가 minimum degree보다 작기 때문에  $G\mathrm{\setminus }C$에 속한 임의의 vertex가 나머지 모든 $G\mathrm{\setminus }C$ vertices에 adjacent해도 그것의 degree가 $\delta$보다 작다는 뜻이다. 즉, 각 $G\mathrm{\setminus }C$에 속한 vertex는 $C$에 속한 vertices 중 적어도 하나와 adjacent하다는 뜻이다. $P$의 끝점 $x$도 $C$에 속한 vertices 중 적어도 하나와 adjacent하다.

$x$와 adjacent할 수 있는 $C$위의 vertices 후보들을 살펴보자. 우선 Lollipop Lemma에 의해 $x$와 인접한 vertex는 $y$와 $m$이하로 떨어져 있으면 안 된다. 따라서 $l$개 중 $2m$개가 제외되어 $l-2m$개가 남는다. 또한 $x$는 consecutive vertices와 adjacent하면 안된다. ($C$가 longest인 것과 모순이 일어나기 때문이다.) 그러면 후보로 총 $(l-2m)/2$개가 남는다.

종합하여 $x$의 degree를 살펴보자.

$$d(x)\le m+\frac{l-2m}{2}=\frac{l}{2}<\frac{n}{2}\le \delta$$

즉, $d(x)<\delta$가 되어 모순이 발생한다.

 

Note. 이 증명은 Dirac 본인이 한 증명이다.

 

Proof 2. By choosing a longest path

$\mathcal{P}=v_0-v_1-\cdots -v_l$가 $G$에서 길이 $l$인 longest path라고 하자. 먼저 $G$에 $l+1$ 길이를 갖는 cycle $C$가 있음을 보일 것이다. 만약 $v_0$와 $v_l$이 adjacent하면 끝난다. 따라서 $v_0$과 $v_l$이 adjacent하지 않다고 가정하자.

$\mathcal{P}$를 가장 긴 path로 골랐기 때문에 $v_0$의 neighbor과 $v_l$의 neighbor 모두 $\mathcal{P}$에 속한다. $X$와 $Y$를 다음과 같이 정의하자:

$$X:=\{v_i:(v_0,v_{i+1})\in E\}$$

$$Y:=\{v_i:(v_i,v_l)\in E\}$$

Intuitive하게 말하자면 $X$는 $v_0$와 adjacent한 vertex들의 이전 vertex들의 집합이고 $Y$는 $v_l$과 adjacent한 vertex들의 집합니다. 어떤 경우에도 $X\cup Y$에는 $v_l$이 포함되지 않으므로

$$|X\cup Y|\le l\le n-1$$

이다. 또한 (Dirac's Theorem의 전제 조건인) $\delta \ge n/2$으로

$$|X|+|Y|=d(v_0)+d(v_l)\ge 2\delta \ge n$$

임을 알 수 있다. 위 두 식을 $|X\cup Y|=|X|+|Y|-|X\cap Y|$과 종합하면

$$|X\cap Y|=|X|+|Y|-|X\cup Y|\le n-(n-1)=1$$

을 알 수 있다. $X\cap Y$에 속한 vertex를 $v_k$라 하자. 그러면 $v_0-\cdots -v_k-v_l-\cdots -v_{k+1}-v_0$는 length $l+1$인 cycle임을 알 수 있다. ($v_k$가 $X,Y$에 속한다는 것으로 $(v_0,v_{k+1}),(v_k,v_l)$ edge들이 $E$에 속한다는 것을 알 수 있다.)

이제 이 cycle $C$가 Hamilton cycle임을 보이자. $C$가 Hamilton cycle이 아니라고 가정하자. $C\cup P$를 lollipop이라고 하자. $P$의 길이를 $m$이라 하자. ($m$은 0이 아니다.) Lollipop Lemma에 의해서 길이 $l+1+m-1=l+m$짜리의 path가 존재한다. 처음에 $G$에서 가장 긴 path $\mathcal{P}$의 길이가 $l$이었기 때문에 모순이 발생한다.

 

Note. 이 증명은 Newman이 1958년에 했다. 그리고 가장 많이 알려진 증명이다.

 

Proof 3. 앞의 두 증명을 조합

$C$를 $G$에서의 longest cycle이라고 하자. 마찬가지로 $C$가 Hamilton cycle이 아니라고 가정하자. 그러면 $G\mathrm{\setminus }C\ne \mathrm{\varnothing }$이다. $C\cup P$를 $(x,y)$-lollipop이라고 하자. (역시나 $P$의 길이는 0이 아니다.) $V_1,V_2,V_3$를 다음과 같이 정의하자.

$$V_1:=V(C)$$

$$V_2:=V(P)\mathrm{\setminus }\{y\}$$

$$V_3:=V(G)\mathrm{\setminus }V(C\cup P)$$

즉, $V_1$은 cycle $C$위의 vertices, $V_2$는 $y$를 제외한 path $P$위의 vertices, $V_3$는 lollipop위의 vertices를 제외한 나머지 vertices다. $d_1(v),d_2(v),d_3(v)$를 각각 $V_1,V_2,V_3$에서의 degree라고 하자. 우리는 다음과 같은 사실을 알 수 있다.

(i) $C$위의 consecutive vertices $v$와 $v+$에 대해서 $x$와 $v$, $y^{+}$와 $v^{+}$가 동시에 adjacent할 수 없다. (더 긴 cycle $\cdots -[y-\cdots -x]-v-\cdots -y^{+}-v^{+}-\cdots$이 생성되기 때문.

$$\therefore d_1(x)+d_1(y^{+})\le |V_1|$$

(ii) $y^{+}$는 (Lollipop Lemma에 의해) $V_2$의 어느 vertex와도 adjacent할 수 없다.

$$\therefore d_2(y^{+})=0$$

(iii) $x$와 $y^{+}$는 $V_3$의 한 vertex와 동시에 adjacent할 수 없다. (더 긴 cycle이 생기기 때문.)

$$\therefore d_3(x)+d_3(y^{+})\le |V_3|$$

여기에 $d_2(x)\le |V_2|-1$이라는 사실을 추가해 종합한다면

$$2\delta \le d(x)+d(y^{+})=\sum _{i=1,2,3}(d_i(x)+d_i(y^{+}))\le |V_1|+|V_2|+|V_3|-1=n-1<n$$

즉, 처음의 가정 $\delta \ge n/2$을 위반한다.

 

Note. 이 증명은 Bondy가 1981년에 했다.

Note. Dirac's Theorem의 inductive proof는 알려진 바가 없다. 

 

Corollary of Dirac's Theorem

$n$ vertices를 가진 simple graph $G$가 $\delta \ge (n-1)/2$를 만족한다고 하자.
그러면 $G$는 Hamilton path를 가진다.

증명은 간단하다. $n=1$이면 trivial하다. $n\ge 2$일 때는 $G$에 새로운 vertex $v$를 추가하고 기존의 모든 vertices와 연결한다. 그러면 resulting graph는 $n+1$의 vertices를 가지고 minimum degree가 at least $(n+1)/2$가 된다. Dirac's Theorem에 의해 길이 $n+1$짜리 Hamilton cycle이 존재하고, 이 cycle에서 $v$를 제거하면 기존의 그래프에서 Hamilton path가 된다.

 

Generalization of Dirac's Theorem

Dirac's Theorem은 다양한 방향으로 generalize될 수 있다. 우선 Proof 2를 살펴보자. 잘 보면 $\delta \ge n/2$ 조건을 (직접적으로) 사용하지 않고 이보다 더 약한 조건인 $d(v_0)+d(v_l)\ge n$을 사용했다. 따라서 똑같은 증명으로 더 stronger theorem을 보일 수 있다.

 

Ore's Theorem.

$n\ge 3$의 vertices를 가지는 simple graph $G$에서 아무 nonadjacent vertices 두 개의 degree를 합했을 때 항상 최소 $n$이면. $G$는 Hamilton cycle을 갖는다.

 

Proof 2를 이용하여 추가적으로 뽑아낼 수 있는 것을 더 찾아보자. $n\ge 3$인 $G$에서 degree의 sum이 최소 $n$인 두 nonadjacent vertices가 존재하고 이를 $u$와 $v$라고 하자. 과연 어떤 조건 하에 $G$에 Hamilton cycle이 있을까?

$G$에 $(u,v)$ edge를 추가한 그래프를 $G^{\prime }$라 하자. 그리고 $G^{\prime }$에서 Hamilton cycle $C^{\prime }$이 있다고 가정하자. 만약 $C^{\prime }$에 $(u,v)$ edge가 없다면 $C^{\prime }$은 $G$에서도 Hamilton cycle이니, $C^{\prime }$에 $(u,v)$가 반드시 포함된다고 가정하자. 이 뜻은 $u$와 $v$를 endpoint로 갖는 path가 있었다는 것이고 이 path의 길이는 $n-1$이었을 것이다. 즉 이 path는 proof 2에서 처음에 고른 longest path $\mathcal{P}$이자 모든 vertex를 지나는 spanning path가 된다. 따라서 proof 2에 따라 $G$도 Hamiltonian이라는 것을 알 수 있다.

 

$n\ge 3$의 simple graph $G$에 nonadjacent하며 degree의 sum이 $n$ 이상인 vertices $u$와 $v$가 있다고 하자. 만약 $G+(u,v)$가 Hamiltonian이라면 $G$도 그러하다.

 

이것을 활용해서 Dirac's Theorem을 더 generalize할 수 있다. 현재 보고 있는 그래프에 nonadjacent하면서 degree의 sum이 $n$ 이상인 두 vertices가 있고 이 둘을 잇는 과정 $proc$라고 했을 때 더 이상 그런 vertices pair가 없을 때까지 $proc$를 반복해서 나온 그래프를 그것의 closure이라고 하자.

 

Closure Lemma (Bondy-Chvátal Theorem)

A simple graph $G$ is Hamiltonian if and only if its closure is Hamiltonian.

 

따라서 만약 어떤 graph $G$의 closure가 complete하다면, (complete graph는 Hamiltonian이기 때문에) $G$는 Hamiltonian이다. 이 이유로 Dirac's Theorem을 만족하는 graph $G$는 (minimum degree가 $n/2$ 이상이므로) closure를 취하면 complete해지기에 Hamiltonian이라 할 수 있다. 이 아이디어를 이용해서 추가적인 사실을 알아보자.

 

Chvátal Theorem

$n\ge 3$인 simple graph $G$가 degree sequence $(d_1,d_2,...,d_n)$를 갖는다고 하자.
($d_1\le d_2\le \cdots \le d_n$.)
만약 $(n-1)/2$ 이하의 $k$ 중에서 $d_k\le k$이고 $d_{n-k}<n-k$인 $k$가 존재하지 않는다면,
$G$는 Hamiltonian이다.

 

조건이 비교적 복잡하지만 천천히 증명해보자. 증명에서는 위의 조건을 만족하는 $G$에 closure를 취했을 때 complete graph임을 모순으로 보인다. $G$의 closure를 complete가 아닌 graph $H$라고 하자. $G$에서의 degree는 $H$에서의 degree보다 크지 않을 테니 $d_G$를 $d_H$로 bound할 수 있고, 따라서 만약 $H$에서 조건에 만족하는 $k$가 존재한다면 $G$에서도 만족한다. 우리는 그런 $k$를 찾아서 모순을 보일 것이다.

$H$의 nonadjacent vertices 중 degree sum이 최대인 vertices pair를 $a$와 $b$라고 하자. $d_H(a)+d_H(b)\le n-1$일 것이다. WLOG, $d_H(a)\le d_H(b)$라고 가정하고 $d_H(a):=k$로 설정하면, $k\le (n-1)/2$일 것이고 $d_H(b)\le n-k-1$일 것이다. 

$H$에서 $a$와 $b$에 nonadjacent한 vertices set을 각각 $\overline{N_H}[a]$, $\overline{N_H}[b]$라고 하자. (자기 자신은 adjacent하다고 생각하자.) 그러면 $$|\overline{N_H}[a]|=n-d_H(a)-1=n-k-1$$

$$|\overline{N_H}[b]|=n-d_H(b)-1\ge k$$

를 만족한다. 추가적으로 $u\in \overline{N_H}[a]$에 대해서 $d_H(u)\le d_H(b)$이어야 하고 $v\in \overline{N_H}[b]$에 대해서 $d_H(v)\le d_H(a)$이어야 한다. (그렇지 않으면 $a$와 $b$의 choice에 모순이 생긴다.) 

$$\mathrm{\forall }u\in \overline{N_H}[a],d_H(u)\le n-k-1$$

$$\mathrm{\forall }v\in \overline{N_H}[b],d_H(v)\le k$$

종합하면 $H$에서 degree가 최대 $n-k-1$인 vertices는 $|\overline{N_H}[a]\cup \{a\}|=n-k$만큼 있고, degree가 최대 $k$인 vertices는 최소 $|\overline{N_H}[b]|=k$만큼 있다. 따라서 $\mathrm{\exists }k\le (n-1)/2$ such that $d_k\le k$ and $d_{n-k}\le n-k-1<n-k$ are satisfied.

 

Closure Lemma를 이용해서 Ore's Theorem의 generalized 버전을 쉽게 증명할 수 있다.

Fan's Theorem

$n\ge 3$인 2-connected simple graph $G$에서 degree가 $n/2$ 미만인 vertices끼리는 common neighbor가 없다면,
$G$는 Hamiltonian이다.

 

Note. Ore's Theorem은 모든 nonadjacent한 vertices의 degree sum이 $n$ 이상이라는 조건을 가졌는데, 이 조건은 2-connectedness를 imply하고 새로운 조건에서는 nonadjacent vertices의 degree sum이 $n$이 안되는 vertices pair가 존재할 수 있기 때문에 generalization이다.

(왜 모든 nonadjacent한 vertices의 degree sum이 $n$ 이상이라는 조건이 2-connectedness를 imply할까?)

2-(vertex-)connected graph는 임의의 vertex를 제거해도 connectedness가 유지되는 graph를 말한다. nonadjacent한 어떤 두 vertices를 잡아도 degree sum이 총 vertex 수 이상이다. 즉 고른 2개의 vertices를 제외한 $n-2$개의 vertices 중에 최소 2개는 common neighbor이다. 따라서 어떤 vertex를 제고해도 disconnect되지 않는다.

 

증명을 해보자. $F$를 degree가 $n/2$이 안 되는 vertices로만 이루어진 subgraph에서의 한 connected component라고 하자. $F$에서 두 vertices $u$와 $v$를 고르고 이 둘 사이의 shortest path를 $P=u-x_1-x_2-\cdots -v$라고 하자. $P$의 길이는 최대 얼마일까? 만약 $P$의 길이가 2 이상이라면, $u$와 $x_2$ 둘 다 degree가 $n/2$ 미만인데, common neighbor를 갖게된다는 모순이 생긴다. 따라서 $P$의 최대 길이는 1, 즉 $F$에서 어떤 두 vertices를 골라도 서로 adjacent하다는 것이다. 이 말은 $n/2$이 안되는 vertices로만 이루어진 subgraph에서 모든 connected component는 complete하다는 것을 알 수 있다.

이제 $G$에 closure를 취해보자. $U$를 degree가 $n/2$ 이상인 vertices set이라 하면, $G$의 closure에서 $U$의 subgraph는 complete하다. 따라서 $F$와 $U$ 사이에 edge가 어떻게 있는지에 따라 $G$의 closure에서 Hamilton cycle 존재성이 갈린다. 주어진 그래프가 2-connected 임을 이용해보자. $|F|=1$면 $U$와 최소 2개의 edge로 이어져 있을 것이다. $|F|\ge 2$면 $U$와 최소 2개의 independent edge, 즉 endpoint가 다 다른 edge들로 이어져 있을 것이다. (만약 endpoint가 같은 edge로 이어져 있다면 그 vertex를 제거했을 때 connectedness가 깨지게 된다.) 이로써 우리는 Hamilton cycle이 존재함을 알 수 있다.

---

Extra.

이제까지는 Dirac's Theorem의 조건을 generalize했다면 이번에는 결과를 generalize하는 정리를 하나 살펴본다. 우선 한 가지 정의를 하고 넘어가자. $3\le \ell \le n$인 모든 $\ell$에 대해서 그래프가 length가 $\ell$인 cycle을 포함한다면 그 그래프는 pancyclic하다. 당연히 pancyclic한 그래프는 Hamiltonian이다. 다음은 이와 관련된 Bondy의 정리이다.

 

Bondy Theorem

$m\ge n^2/4$를 만족하는 simple Hamiltonian graph $G$는
(1) pancyclic하거나 (2) complete bipartite graph이다.

 

증명은 induction으로 진행된다. $n=3$이면 trivial하다. 따라서 $n\ge 4$일 때를 가정하자.

 

1. $G$가 $n-1$ 길이의 cycle을 포함하면 $G$는 pancyclic하다.

그 cycle을 $C=v_1-v_2-\cdots -v_{n-1}-v_1$라고 하고 $v$를 $C$에 속하지 않은 $G$의 vertex라고 하자.

$G^{\prime }=G\mathrm{\setminus }\{v\}$라고 정의하고 $G^{\prime }$의 vertex 수와 edge 수를 각각 $n^{\prime },m^{\prime }$이라고 하자.

• 만약 $d(v)\le (n-1)/2$라면,
  $$m^{\prime }=m-d(v)\ge \frac{n^2}{4}-\frac{n-1}{2}>\frac{(n-1{)}^2}{4}=\frac{n^{\prime }}{4}$$를 만족한다. Induction hypothesis에 의해 $G^{\prime }$는 pancyclic하고, 따라서 $G$는 pancyclic하다.
  (Induction hypothesis에 따르면 $G^{\prime }$가 complete bipartite graph일 수 있다. 하지만 $|E|>|V{|}^2/4$인 경우 그래프가 complete bipartite일 수 없고 $m^{\prime }>n^{\prime 2}/4$이기 때문에 $G^{\prime }$는 complete bipartite graph가 아님을 알 수 있다.
• 만약 $d(v)>(n-1)/2$라면,
  $3\le \ell \le n$를 만족하는 모든 $\ell$에 대해서, $C$에 속하면서 서로 $\ell -2$만큼 떨어져 있고 $v$에 adjacent하는 두 vertex $v_i,v_{i+\ell -2}$가 존재한다. (이것의 증명은 아래에 있다.) 따라서 길이가 $\ell$인 cycle $v-v_i-\cdots -v_{i+\ell -2}-v$이 존재하기 때문에, $G$는 pancyclic하다.
  이것의 증명에서는 어떤 $\ell$에 대해서는 그러한 $i$가 없다고 가정을 하고 모순을 보인다. $v$에 adjacent한 vertex들을 $v_{i_1},v_{i_2},\cdots ,v_{i_{d(v)}}$라고 하자. $r:=\ell -2$라고 했을 때, 가정에 따라 $v$는 모든 $v_{i_1+r},v_{i_2+r},\cdots ,v_{i_{d(v)}+r}$과 adjacent하지 않을 것이다. (만약 v의 subscript index가 n-1을 넘어가면 modulo를 취한다.) $v$와 adjacent한 vertex의 수가 $d(v)$이고 nonadjacent한 vertex의 수도 최소 $d(v)$이기 때문에 cycle 위의 vertex의 수는 최소 $2d(v)$이다. 그러나 $d(v)>(n-1)/2$이기 때문에 모순이 발생한다.

2. $G$가 $n-1$ 길이의 cycle을 포함하지 않으면 complete bipartite하다. (물론 $n$은 짝수여야 한다.)

$v_1-v_2-\cdots -v_n-v_1$을 $G$의 Hamilton cycle이라고 하자. 그러면 $1\le i,j\le n$이면서 $j\ne i-1$인 모든 $i,j$에 대해서, $(v_i,v_j)$와 $(v_{i+1},v_{j+2})$ 중 최대 하나만이 $G$의 edge가 될 수 있다. (그렇지 않으면 $v_j-v_{j-1}-\cdots -v_{i+1}-v_{j+2}-v_{j+3}-\cdots -v_i-v_j$인 cycle이 존재하고 이것의 길이는 $n-1$이다.)

이제 $v_i$와 $v_{i+1}$에 adjacent한 vertex의 수의 관계를 보자. $v_i$가 $v_j$에 adjacent하면 $v_{i+1}$은 $v_{j+2}$와 adjacnet하지 않다. $v_i$가 $d(v_i)$만큼 adjacent하면 $v_{i+1}$은 최소 $d(v_i)$만큼 nonadjacent하다. 따라서 $$d(v_i)+d(v_{i+1})\le n$$을 만족한다. 모든 $i$에 대해서 위 식을 합치면 $$2\sum _{i=1}^{n}d(v_i)\le n^2$$이 될 것이고 $\sum _{i=1}^{n}d(v_i)=2m$인 것을 이용하면 $$m\le \frac{n^2}{4}$$를 얻을 수 있다. $G$의 조건 중 하나인 $m\ge n^2/4$에 의해 $m=n^2/4$임을 알 수 있고, 이를 통해 모든 $i$에 대해 $d(v_i)+d(v_{i+1})=n$임을 알 수 있다. 따라서 $1\le i,j\le n$이면서 $j\ne i-1$인 모든 $i,j$에 대해서, $(v_i,v_j)$와 $(v_{i+1},v_{j+2})$ 중 최대 하나만이 $G$의 edge가 될 수 있다는 조건에서 '정확히 하나'를 만족하는 조건으로 강화됨을 알 수 있다.

이제 이를 이용해 complete bipartite임을 보이자. 일단 그래프가 bipartite하지 않다고 가정하자. 그러면 $i\equiv j(\mathrm{mod}2)$이면서 $v_i$와 $v_j$가 adjacent한 $i,j$가 존재할 것이다. 그러한 $i,j$ 중에 $|i-j|$가 가장 작은 pair를 $i^{\prime },j^{\prime }$라고 하자. (WLOG, $i^{\prime }<j^{\prime }$라고 가정하자.) 우선 $j^{\prime }-i^{\prime }$는 2가 될 수 없다. 왜냐하면 길이 $n-1$ cycle이 생기기 때문이다. $j^{\prime }-i^{\prime }$는 4이상의 짝수인데 그러면 $v_{i^{\prime }}$와 $v_{j^{\prime }}$가 adjacent하다는 것으로 $v_{i^{\prime }-1}$과 $v_{j^{\prime }-2}$는 nonadjacent함을 알 수 있고, 이것으로 $v_{i^{\prime }-2}$과 $v_{j^{\prime }-4}$가 adjacent함을 알 수 있다. 여기서 $i^{\prime },j^{\prime }$의 선택에 모순이 생긴다.

Bipartite하면서 $m=n^2/4$를 만족하는 그래프는 complete bipartite graph밖에 없다.

---

Reference - Handbook of Combinatorics, Volume 1, Basic graph theory: Paths and circuits