Degree Sequence
어떤 그래프 \(G\) 의 degree sequence는 각 점의 degree로 이루어지는 non-decreasing sequence이다. 즉, 이 sequence의 길이는 그래프의 꼭짓점의 수 \(V(G)\)가 된다. 분명 임의의 그래프가 주어졌을 때 degree sequence를 결정할 수 있지만, degree sequence에서 대응되는 그래프가 하나, 즉 대응되는 그래프가 모두 isomorphic 한지는 조금 생각해볼 문제이다. 이후 증명에서 나오겠지만 대응되는 그래프는 일반적으로 많이 나타난다.
그 전에, degree sequence에서 그래프가 대응되는가도 확실하지 않다. 예를 들어 (1,1,1,1,1)은 대응되는 그래프가 존재하지 않는다.
\[ \sum _{v \in V} \deg (v) = 2|E| \]
좌변이 홀수가 되기 떄문이다. 그렇다고 degree의 총합이 짝수가 된다고 그 degree sequence를 만족하는 그래프가 존재하는가는 또 확실하지 않다.
따라서 degree sequence를 만족하는 그래프를 찾는 문제가 있고, 생각보다 어렵다. 모든 점을 동시에 고려하기 때문인데, 점 하나만 고려하도록 하는 귀납적 형태로 문제의 축소를 생각할 수 있다.
Theorem. \(d_1 , \cdots d_n \)은 어떤 그래프의 degree sequence라면, \(d_2 -1, d_3 -1, \cdots , d_{d_1 +1} -1, d_{d_1 +2}, \cdots , d_n \)도 어떤 그래프의 degree sequence이고, 그 역도 성립한다.
proof. \((\Leftarrow)\)
만약 \(d_2 -1, d_3 -1, \cdots , d_{d_1 +1} -1, d_{d_1 +2}, \cdots , d_n \) 이 어떤 그래프 \(G(V,E)\)의 degree sequence라면 일반성을 잃지 않고 \(V = \{2,3,\cdots ,n \}\)으로 놓자. 새로운 그래프 \(G'(V',E')\)을 생각해서
\[ V' = \{1,2,3,\cdots,n \} \]
\[ E' = E \sqcup \{ \{ 1,2 \}, \{ 1,3\}, \cdots , \{ 1, d_1 +1\} \} \]
이 되도록 할 수 있고 이 그래프의 degree sequence는 \(d_1 , \cdots d_n \)이다. \(\square\)
\((\Rightarrow )\)
이 방향은 반대쪽과 달리 non-trivial하기 때문에 이 정리가 가치 있는 이유가 된다.
degree sequence \(d_1 , \cdots ,d_n\)을 가지는 한 그래프에 대해 순서대로 대응되는 점을 \(\{v_1,v_2, \cdots, v_n \} \)으로 놓자. \(v_1\)과 연결되는 점이 \(v_2, \cdots , v_{d_1 +1 } \)이라면 명제가 당연히 성립한다. 점 하나를 빼는 것과 같기 때문이다.
따라서 \(v_1\)과 연결되는 점의 집합이 \(S = \{v_2 , \cdots ,v_{d_1+1 } \} \)과 다를 경우만 고려하면 된다. \(v_1\)과 연결되는 점 중 \(S\)에 없는 점을 \(x\), \(S\)에 있지만 \(v_1\)에 연결되지 않은 점을 \(y\)로 놓자. degree sequence가 non-decreasing이기 때문에 다음이 성립한다.
\[ \deg (x) \ge \deg (y) \]
그런데 \(x\)는 이미 \(v_1\)에 연결되었으므로 \(y\)와 연결되었지만 \(x\)에는 연결되지 않은 \(x,y,v_1\)이 아닌 다른 한 점 \(z\)가 존재한다. 즉, 이 부분에 대해 subgraph \(G_{sub} \)는 다음과 같이 정의된다.
\[ V(G_{sub} ) = \{ v_1, x, y, z \} \]
\[ E(G_{sub} ) = \{ \{ v_1, x \}, \{ y,z \} \} \]
전체 그래프에서 \(G_{sub}\)만 complement를 취해주면 각 점의 degree는 보존되고 \(\{v_1, y \} \)가 생긴다.
이런 과정을 \(S\)안의 모든 점에 대해 시행해주면 \(S\)의 모든 점이 \(v_1\)과 연결되고 이 그래프는 자명하게 정리를 만족한다. \(\square \)