13. 一個沒方向性的連接圖，節點為N，則其邊的個數不可能為
(A) N-2
(B) N-1
(C) N
(D) N+1

【解題思路】

關鍵觀念：

無向連通圖（connected graph）
邊數的可能範圍：

最少邊數（形成連通）：

N − 1
→ 這是樹（Tree）的邊數。

最多邊數（形成完全圖）：

N(N−1)/2
→ 每兩點都相連。

所以：

邊的個數可能從 N−1 起跳，不能更少。

因此：

N−2 是不可能的，因為比「連通所需的最少邊數 N−1」還少，會變成不連通。

【逐一破題】

(A) N−2
→ 不可能
→ 比最少邊數（N−1）還少，會斷掉，變成不連通。
→ 正確答案。

(B) N−1
→ 可能 → 樹的邊數就是 N−1。
→ 錯選。

(C) N
→ 可能 → 比樹多一條邊，就變成含一個環的連通圖。
→ 合法。

(D) N+1
→ 可能 → 邊數更大仍可連通（甚至多個環）。
→ 合法。

【延伸知識】

無向連通圖 Edges（E）範圍：

N−1 ≤ E ≤ N(N−1)/2

其中：

• E = N−1 → Tree（無環）

• E > N−1 → Connected Graph with cycles

• E = N(N−1)/2 → 完全圖 Kₙ

因此「唯一不可能」的就是 **少於 N−1」。

【記憶技巧】

一句話：

連通最少邊 N−1，再少一定斷。

【常見錯誤】

1. 以為 N 是最少 → 錯，最少是 N−1

2. 以為連通圖不允許 N+1 → 錯，多邊照樣可以連通

3. 忘記「樹」的邊數是 N−1 → 這是經典