부경대 2021 이산수학 기말

1. K3,3 그래프가 평면 그래프가 아님을 증명하세요.

K3,3 그래프가 평면 그래프가 아님을 증명하기 위해서는 주어진 그래프가 아무리 평면적으로 그려도 서로 교차하지 않도록 그릴 수 없다는 것을 보이면 된다. K3,3 그래프는 두 개의 정점 집합이 각각 3개의 정점으로 이루어져 있으며, 이 정점 집합 간의 모든 가능한 간선이 연결된 형태이다. 그래서 K3,3 그래프는 총 6개의 정점과 9개의 간선을 가진다. 이 그래프의 정점 집합을 A = {a1, a2, a3}와 B = {b1, b2, b3}로 두고, 각 점들을 연결하는 간선은 A 집합의 모든 정점이 B 집합의 모든 정점과 연결된 형태를 가지고 있다. K3,3 그래프가 평면 그래프가 아님을 증명하기 위해서는 Kuratowski의 정리를 이용하는 것이 유용하다. Kuratowski의 정리에 따르면, 어떤 그래프 G가 평면 그래프가 아니라면, G는 K5(완전 그래프에서 5개의 정점) 또는 K3,3(양쪽이 3개의 정점으로 이루어진 완전 이분 그래프)의 서브그래프를 포함해야 한다. 따라서 K3,3의 성질을 살펴보면, 이 그래프가 평면적이지 않음을 직접적으로 보일 수 있다. K3,3을 평면적으로 그린다고 가정했을 때, 모든 간선이 서로 교차하지 않도록 그려…