정답
조건을 만족하면서 \(\displaystyle \sum_{n=1}^7 \deg(v_n)\) 이 최대가 되도록 할 때, 그래프 \(G\) 의 변의 개수는 \(8\)개이다.
출제 의도
완전그래프와 완전이분그래프의 색채수 성질을 이용하여 각 꼭짓점의 차수 상한을 구하고, 단순그래프에서 차수들의 합이 항상 짝수이자 \(2|E|\) 와 같다는 사실을 사용하여 변의 최대 개수를 구하게 하는 문제이다. 또한 실제로 그 최대값이 실현되는 차수열과 그래프 구성을 확인하는 사고력을 평가한다.
풀이 과정
주어진 조건에서 먼저 완전그래프와 완전이분그래프의 색채수를 사용한다.
\(K_n\) 의 색채수는 \(\chi(K_n)=n\), \(K_{n,n}\) 의 색채수는 \(\chi(K_{n,n})=2\) 이다.
조건 (가)에 의해
\[ n\in\{1,7\} \Rightarrow \deg(v_n)\le \chi(K_n). \]
따라서
\[ \deg(v_1)\le 1,\qquad \deg(v_7)\le 7. \]
하지만 단순그래프에서 한 꼭짓점의 차수는 최대 \(6\) 이므로 실제로는 \(\deg(v_7)\le 6\) 이다.
조건 (나)에 의해
\[ n\in\{2,3,4,5,6\}\Rightarrow \deg(v_n)\le \chi(K_{n,n})=2 \]
이므로
\[ \deg(v_2),\deg(v_3),\deg(v_4),\deg(v_5),\deg(v_6)\le 2 \]
이다.
이제 \(\sum_{n=1}^7\deg(v_n)\) 의 최대값을 생각하자. 위의 상한을 모두 채우면
\[ \deg(v_1)=1,\quad \deg(v_2)=\cdots=\deg(v_6)=2,\quad \deg(v_7)=6 \]
으로서 차수 합의 상한은
\[ 1+5\cdot 2+6 = 17 \]
이다. 그러나 단순그래프에서는 항상
\[ \sum_{n=1}^7\deg(v_n)=2|E| \]
이므로 차수의 합은 짝수여야 한다. 따라서 실제로 가능한 최대 합은 \(17\)보다 작으면서 짝수인 \(16\) 이다.
즉
\[ \sum_{n=1}^7\deg(v_n)\le 16,\qquad |E|\le \frac{16}{2}=8 \]
이다. 이제 이 상한 \(16\)이 실제로 실현될 수 있는지 차수열을 하나 만들어 보자.
위에서 상한 하나만 1 줄여서
\[ (\deg(v_1),\deg(v_2),\deg(v_3),\deg(v_4),\deg(v_5),\deg(v_6),\deg(v_7)) = (1,2,2,2,2,2,5) \]
로 두면 합이
\[ 1+5\cdot 2+5 = 16 \]
이 되어 제약을 모두 만족한다. 이 차수열이 실제 그래프에서 가능함을 보이기 위해 하나의 구성을 제시한다.
먼저 \(\deg(v_7)=5\) 가 되도록 \(v_7\) 을 \(v_2,v_3,v_4,v_5,v_6\) 에 모두 잇는다.
그러면 현재 차수는
\[ \deg(v_2)=\cdots=\deg(v_6)=1,\quad \deg(v_1)=0,\quad \deg(v_7)=5 \]
이 된다. 이제 나머지 꼭짓점 \(v_1,\dots,v_6\) 의 차수가 모두 1이 되도록
\[ v_1v_2,\quad v_3v_4,\quad v_5v_6 \]
의 세 변을 추가한다. 그러면 최종 차수는
\[ \deg(v_1)=1,\; \deg(v_2)=\cdots=\deg(v_6)=2,\; \deg(v_7)=5 \]
가 되어 위에서 정한 차수열이 그대로 실현된다. 따라서
\[ \sum_{n=1}^7\deg(v_n)=16,\qquad |E|=\frac{16}{2}=8 \]
이 가능하고, 앞에서 보았듯이 이것이 최대이다.
결론적으로, 조건을 만족하는 그래프 \(G\) 에서 변의 최대 개수는 \(8\)개이다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>