Membuktikan Pertanyaan Teori Grafik

Question

Saya tidak dapat memberikan bukti terkait pernyataan ini -

Pertimbangkan G sebagai grafik planar terhubung. Jika G bukan bipartit, maka setiap embedding planar dari G memiliki minimal 2 sisi dengan derajat ganjil.

Bisakah seseorang membantu saya dengan buktinya?

Answer 1

Karena G bukan bipartit, G mengandung siklus ganjil C. Let $F_{1},F_{2},......,F_{k}$menjadi wajah di dalam C di embedding planar. Pertimbangkan jumlah derajat wajah ini.

• Setiap sisi di C dihitung sekali.
• Misalkan D menjadi himpunan tepi pada setiap batas dari apapun $F_{i}$, tapi tidak di C.

Setiap sisi di D dihitung dua kali.

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

Sejak $|E(C)|$ aneh dan $2|D|$ genap,

$\sum_{i}$ $\deg(F_{i})$ itu aneh, jadi $\deg(F_{i})$ pasti aneh bagi sebagian orang $i$

Jadi setidaknya satu wajah di dalam C memiliki derajat ganjil.

Argumen yang sama dapat digunakan untuk menunjukkan bahwa setidaknya sekali wajah di luar C memiliki derajat ganjil.