쿠라토프스키 정리

[부끄러운 임고생]

그래프가 평면그래프인지 아닌지 판정할 때 K_5, K_3,3을 부분그래프로 갖고있는지 확인하잖아요..??

근데 이를 그래프로 관찰할 때는 원래의 그래프도 복잡해서 완전그래프랑 완전이분그래프가 잘 보이지 않는데,,, 행렬로 표현해보니 좀 보이는거 같기도한 것 같은데
그 근거가 명확하지 않은채 애매하게 잡혀있어서 질문드립니다!

주어진 그래프의 인접행렬의 소행렬 중 다음과 같은 행렬이 존재하면 그 그래프는 평면 그래프라고 아니다 라고 할 수 있을까요?

[박정환]

네

[부끄러운 임고생]

감사합니다~