📂그래프이론

쾨닉의 정리 증명

정리 ¹

$G$ 가 국소적으로 유한인 연결 그래프라고 하자. 그러면 모든 $v \in V(G)$ 에 대해 $v$ 가 시점인 원웨이 무한 패스가 존재한다.

증명

$G$ 는 연결 그래프이므로 $v$ 가 아닌 모든 $z \in V(G)$ 에 대해 $v$ 에서 $z$ 로 가는 패스가 무한히 많이 존재한다. 그리고 $G$ 는 국소적으로 유한하므로 무한히 많은 패스들 중 무한히 많은 일부는 하나의 같은 에지로 시작해야만한다. 그 에지를 $vv_{1}$ 이라고 하자. 그러면 같은 방식으로 새로운 에지 $v_{1}v_{2}$ 를 잡을 수 있다. 이를 통해 다음의 원웨이 무한 패스를 얻는다. $$v \to v_{1} \to v_{2} \to \cdots$$

■