ग्राफ थ्योरी प्रश्न को साबित करना
मैं इस कथन के बारे में एक प्रमाण के साथ नहीं आ पा रहा हूँ -
विचार करें कि G एक जुड़ा हुआ प्लानर ग्राफ है। यदि G द्विपदी नहीं है, तो G के किसी भी प्लानर एम्बेडिंग में विषम डिग्री वाले कम से कम 2 चेहरे हैं।
क्या कोई मुझे प्रमाण के साथ मदद कर सकता है?
जवाब
चूँकि G द्विदलीय नहीं है, G में एक विषम चक्र C. Let है $F_{1},F_{2},......,F_{k}$प्लानर एम्बेडिंग में C के अंदर के चेहरे हों। इन चेहरे की डिग्री के योग पर विचार करें।
- C में प्रत्येक किनारे को एक बार गिना जा रहा है।
- आज्ञा देना किसी के किसी भी सीमा पर किनारों का सेट हो $F_{i}$, लेकिन सी पर नहीं।
डी में प्रत्येक किनारे को दो बार गिना जाता है।
इसलिए $\sum_{i}$ $\deg(F_{i})$ = $|E(C)| + 2|D|$
जबसे $|E(C)|$ अजीब है और $2|D|$ सम है,
$\sum_{i}$ $\deg(F_{i})$ अजीब है, इसलिए $\deg(F_{i})$ कुछ के लिए अजीब होना चाहिए $i$
इसलिए C के अंदर कम से कम एक चेहरे के पास विषम डिग्री है।
एक ही तर्क का उपयोग यह दिखाने के लिए किया जा सकता है कि सी के बाहर कम से कम एक बार विषम डिग्री है।