그래프 이론 질문 증명

Question

이 진술에 대한 증거를 찾을 수 없습니다.

G를 연결된 평면 그래프라고 생각하십시오. G가 2 분할이 아닌 경우 G의 평면 임베딩에는 홀수 차수가있는면이 2 개 이상 있습니다.

누군가 증거로 나를 도울 수 있습니까?

Answer 1

G는 이분자가 아니므로 G는 홀수주기 C를 포함합니다. $F_{1},F_{2},......,F_{k}$평면 임베딩에서 C 내부의면입니다. 이 얼굴의 각도 합계를 고려하십시오.

• C의 각 모서리는 한 번 계산됩니다.
• D를 모든 경계의 가장자리 집합으로 $F_{i}$,하지만 C에서는 아닙니다.

D의 각 모서리는 두 번 계산됩니다.

그래서 $\sum_{i}$ $\deg(F_{i})$ = $|E(C)| + 2|D|$

이후 $|E(C)|$ 이상하고 $2|D|$ 짝수이다,

$\sum_{i}$ $\deg(F_{i})$ 이상하므로 $\deg(F_{i})$ 일부에게는 이상 할 것입니다 $i$

따라서 C 내부의 적어도 하나의 얼굴은 이상한 차수를가집니다.

동일한 인수를 사용하여 C 외부의 얼굴이 홀수 차수를 갖는 것을 적어도 한 번 보여줄 수 있습니다.