Kanıtlanmış Grafik Teorisi Sorusu

Question

Bu ifadeyle ilgili bir kanıt bulamıyorum -

G'yi bağlantılı bir düzlemsel grafik olarak düşünün. G iki taraflı değilse, G'nin herhangi bir düzlemsel gömülmesinin tek dereceli en az 2 yüzü vardır.

Kanıt konusunda biri bana yardım edebilir mi?

Answer 1

G iki taraflı olmadığından, G tek bir C döngüsü içerir. $F_{1},F_{2},......,F_{k}$düzlemsel yerleştirmede C içindeki yüzler olabilir. Bu yüzlerin derecelerinin toplamını düşünün.

• C'deki her kenar bir kez sayılır.
• D herhangi bir sınırın herhangi bir sınırındaki kenarlar kümesi olsun $F_{i}$ama C'de değil.

D'deki her kenar iki kez sayılır.

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

Dan beri $|E(C)|$ garip ve $2|D|$ eşittir

$\sum_{i}$ $\deg(F_{i})$ tuhaf, yani $\deg(F_{i})$ bazıları için garip olmalı $i$

Yani C'nin içindeki en az bir yüzün tuhaf derecesi var.

Aynı argüman, C dışındaki en az bir yüzün tek dereceli olduğunu göstermek için kullanılabilir.