정답
㉠ b, ㉡ f, ㉢ e7, ㉣ e10
출제 의도
그래프 동형에서는 정점의 차수와 인접 관계가 보존되어야 함을 이용해 동형 여부를 판별하고, K3,3을 부분 그래프로 가지면 평면 그래프가 될 수 없다는 성질을 활용하여 특정 간선을 제거해 K3,3의 존재를 확인하는 능력을 평가한다.
풀이 과정
(다)에서 GL은 차수 3인 두 정점 A와 B가 간선으로 서로 연결되어 있다. 따라서 GR이 GL과 동형이라면, GR에도 “차수 3인 두 정점이 서로 인접”하는 쌍이 존재해야 한다.
GR에서 차수 3인 정점은 b와 f이며, 이 두 정점 b와 f는 서로 간선으로 연결되어 있지 않다. 따라서 차수 3 정점 사이의 인접 관계가 보존될 수 없으므로 동형조건2를 만족하는 함수 f가 존재하지 않아 GL과 GR은 동형이 아니다.
(라)에서 (가)를 올바르게 표현한 그래프는 GL이다. GL에서 정점 집합을 \(\{A,D,F\}\)와 \(\{B,C,E\}\)로 나누면 두 집합 사이의 간선 9개는 모두 존재하여 \(K_{3,3}\)의 형태가 된다. 다만 같은 집합 내부를 잇는 간선이 있으면 이분 그래프가 아니므로 이를 제거해야 한다.
집합 \(\{B,C,E\}\) 내부의 간선은 \(CE\)이고, 이는 \(e7\)이다. 집합 \(\{A,D,F\}\) 내부의 간선은 \(DF\)이고, 이는 \(e10\)이다. 따라서 GL에서 \(e7\)과 \(e10\)을 제거하면 \(K_{3,3}\)이 남고, GL은 \(K_{3,3}\)을 부분 그래프로 가지므로 평면 그래프가 아니다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>