이언배 연구노트

그래프를 종이에 그릴 수 있겠니? 선이 겹치면 헷갈리잖아. 규칙을 몇 개 정해줄게. DefinitionDrawing a multigraph두 edge 를 crossing: 공통의 internal point 가진다는 것emdgedding: crossing 이 없는 drawingplanar: multigraph 가 plane 에 embed 가능plane multigraph: multigraph 를 planar embedding 하게 그린 예시"안겹치게 잘 그려봐" Proposition$K_5$ 랑 $K_{3, 3}$ 은 planar 그래프가 아니다.5개짜리 complete graph 랑 3대3 complete bigraph 는 안겹치고는 못 그린다.$\textit{Proof}$$C$ 라는 spanning c..