設G是有n個結點,n條邊的簡單連通圖,且G中存在度數為3的結點.證明:G中至少存在有一個度數為1的結點.

設G是有n個結點,n條邊的簡單連通圖,且G中存在度數為3的結點.證明:G中至少存在有一個度數為1的結點.

反證法.假設G中不存在度數為1的結點,G是連通圖,所以G的結點的度數至少是2.
G有3度節點,所以G的所有結點的度數之和大於等於2(n-1)+3=2n+1.
而G有n條邊,度數之和是2n.
衝突.
所以G中至少存在有一個度數為1的結點.