두 그래프 변의 개수 차

[출제의도] 주어진 조건을 만족시키는 그래프를 추론한다. 행렬 $P + Q$의 모든 성분의 합이 $18$이므로 $a + b + c + d + 10 = 18$ $a + b + c + d = 8$ … ㉠ 그래프를 나타내는 행렬 $P , Q$의 각 성분은 $0$ 또는 $1$이므로 행렬 $P + Q$의 성분이 가질 수 있는 값은 $0$, $1$, $2$이다. 이때, ㉠에 의해 $a = b = c = d = 2$이므로 두 행렬 $P , Q$의 $( 1 , 2 )$성분, $( 2 , 1 )$성분, $( 3 , 4 )$성분, $( 4 , 3 )$성분은 모두 $1$이다. 또한, 행렬 $P + Q$에서 $( 2 , 3 )$성분과 $( 3 , 2 )$성분이 $2$이므로 두 행렬 $P , Q$의 $( 2 , 3 )$성분과 $( 3 , 2 )$성분은 모두 $1$이다. 그러므로 두 행렬 $P , Q$가 나타내는 그래프는 각각 적어도 $3$개의 변을 가진다. ∴ $p \geq 3$, $q \geq 3$ … ㉡ 행렬 $P + Q$의 모든 성분의 합이 $18$이므로 $p + q = 9$이다. ㉡에서 $p = 6$, $q = 3$ 또는 $p = 3$, $q = 6$일 때, $| p - q |$의 최댓값은 $3$이다. [참고] 조건을 만족시키는 두 행렬은 각각 $\displaystyle {\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}}$, $\displaystyle {\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}}$ 이다.