อ้างอิง:
ข้อความเดิมเขียนโดยคุณ PURE MATH
4. ให้ $G$ เป็นซิลเปิลกราฟซึ่งมี $p$ จุด $(p\geqslant 2)$ และทุกๆจุด $v$ ของ $G$ จะมี $d(v)\geqslant \frac{p-1}{2} $ จงพิสูจน์ว่า $G$ เป็นคอนเนคเตดกราฟ
|
ข้อ 4 จะสื่อว่า ทุกจุดของ G มีดีกรี $ \geq \frac{p-1}{2}$ หรือเปล่าครับ
ถ้าใช่ ใช้ Contradiction ครับ
สมมติ G not connected แสดงว่า G มี at least 2 components
Take u ,v จาก 2 components ต่างกัน แน่นอนว่า u,v ไม่มี path เชื่อมถึงกัน ....(*)
Define N(x) แทนเซตของจุดที่ มีเส้นเชื่อมกับ x ดังนั้น $ | N(u) \cup N(v) | \leq p-2 $ (By (*))
By inclusion-exclusion principle , $ | N(u) \cup N(v) | = |N(u)| +| N(v)| - | N(u) \cap N(v)| \geq \frac{p-1}{2} + \frac{p-1}{2} - | N(u) \cap N(v)| $
ดังนั้น $| N(u) \cap N(v)| \geq 1 $ CONTRADICTION WITH (*)