ข้อสอง
ให้ $G$ เป็น simple graph โดยที่ จำนวนจุดยอดของกราฟ $G$ คือ $p$ โดยที่ $p$ เป็นจำนนวนคู่ และ $G_1$ และ $G_2$ เป็น component ของกราฟ $G$
ให้ $G_1$ และ $G_2$ เป็น complete graph
ต้องการจำนวนเส้นเชื่อมที่น้อยที่สุด ดังนั้น จำนวนจุดยอดของ กราฟ $G_1$ และกราฟ $G_2$ ต้องเท่ากัน และมีค่าเท่ากับ $\frac{p}{2}$
(จำนวนเส้นเชื่อมของ complete graph $K_{n}$=$\frac{n(n-1)}{2}$ )
ดังนั้น จำนวนเส้นเชื่อมของกราฟ $G$ = $2\frac{\frac{p}{2}(\frac{p}{2}-1)}{2}=\frac{p^{2}-2p}{4}$
|