圖、節點和邊

一個具有三個頂點和三條邊的簡單無向圖。每個頂點的度數為二，因此它也是一個正則圖。

一個圖是一個有序對 $G=(V,E)$ ，其中：

V 是頂點集，其元素是圖的頂點或節點。這個集合通常用 $V(G)$ 或簡寫為 $V$ 表示。
E 是邊集，其元素是圖的邊或頂點之間的連線。這個集合通常用 $E(G)$ 或簡寫為 $E$ 表示。如果圖是無向的，個體邊是無序對 $\left\{u,v\right\}$ ，其中 $u$ 和 $v$ 是 $V$ 中的頂點。如果圖是有向的，邊是有序對 $(u,v)$ 。

兩個圖 $G$ 和 $H$ 被認為相等，當 $V(G)=V(H)$ 和 $E(G)=E(H)$ 。

圖的階數是指圖中頂點的數量，通常用 $|V|$ 或 $|G|$ 表示，有時也用 $n$ 表示。圖的邊數是指圖中邊的數量，用 $|E|$ 或 $\Vert G\Vert$ 表示，有時也用 $m$ 表示。如果 $n=0$ 和 $m=0$ ，該圖被稱為空圖或零圖。如果 $n=1$ 和 $m=0$ ，該圖被稱為平凡圖。如果 $1\leq n$ 和 $m=0$ ，該圖被稱為離散圖。

無向圖

無向圖是指邊沒有方向的圖。邊 (a, b) 與邊 (b, a) 相同，即它們不是有序對，而是頂點 {u, v}（或 2-多重集）的集合。

有向圖

有向圖或有向圖是一個有序對 D = (V, A) ，其中

V 是一個集合，其元素被稱為頂點或節點，並且
A 是一個頂點有序對的集合，稱為弧、有向邊或箭頭。

弧 a = (x, y) 被認為是從 x 指向 y 的；y 被稱為弧的頭部，x 被稱為弧的尾部；y 被稱為 x 的直接後繼，x 被稱為 y 的直接前驅。如果一條路徑從 x 到 y，則 y 被稱為 x 的後繼，並且可以從 x 到達，而 x 被稱為 y 的前驅。弧 (y, x) 被稱為弧 (x, y) 反向。

如果對於 D 中的每個弧，相應的反向弧也屬於 D，則有向圖 D 被稱為對稱。一個對稱的無環有向圖 D = (V, A) 等價於一個簡單的無向圖 G = (V, E)，其中 A 中的反向弧對一一對應於 E 中的邊；因此，G 中的邊數量 |E| = |A|/2，即 D 中弧數量的一半。

這個定義的一個變體是有向圖，其中 (x, y) 和 (y, x) 中最多隻有一個可以是弧。

示例

在影像中，你可以看到一個圖。

圖的頂點集是 $V(G)=\left\{1,2,3,4,5,6\right\}$ .

圖的邊集是 $E(G)=\left\{\left\{1,2\right\},\left\{1,5\right\},\left\{2,3\right\},\left\{2,5\right\},\left\{3,4\right\},\left\{4,5\right\},\left\{4,6\right\}\right\}$ .

該圖的階數是 $|V(G)|=6$ .

該圖的大小是 $|E(G)|=7$ .

子圖、收縮和圖的次圖

子圖

給定一個圖 $G=(V,E)$ 和一個圖 $G'=(V',E')$ ， $G'$ 是 $G$ 的子圖當且僅當 $V'\subseteq V$ 且 $E'\subseteq E$ 。由此可以明顯看出，每個圖 $G$ 至少包含空圖和自身作為子圖，因為空圖 $\varepsilon$ 的頂點集和邊集都是空集，它們都是所有集合的子集，並且 $V(G)\subseteq V(G)$ 且 $E(G)\subseteq E(G)$ 。此外，某個圖 $G$ 的所有子圖 $G'$ 都可以透過從 $G$ 中進行一系列邊刪除和頂點刪除操作來構造。形式上，存在一個序列 $G_{0},G_{1},...,G_{n}$ ，其中 $G_{0}=G$ 且 $G_{n}=G'$ ，對於每個 $1\leq i\leq n$ ，都是透過從 $G_{i-1}$ 中刪除一條邊或一個頂點來構造的。

邊收縮

給定一個圖 $G=(V,E)$ ，以及圖中頂點 $x,y$ 之間的某條邊 $e$ ，透過收縮邊 $e$ 得到的圖是圖 $G'$ ，其頂點集等於 $V\setminus \{x,y\}\cup \{v_{xy}\}$ ，其中 $v_{xy}$ 是收縮 $e$ 所形成的頂點，它與 $x$ 的所有鄰居以及 $y$ 的所有鄰居相鄰。

圖的子圖

給定一個圖 $G$ ，以及另一個圖 $G'$ ， $G'$ 被稱為 $TG$ ，如果 $G'$ 是透過在 $G$ 的邊中插入度數為 2 的頂點形成的。這個過程稱為 **細分**， $G$ 的頂點被稱為 $G'$ 的 **分支頂點**，而 $G'$ 中的其他頂點被稱為 **細分頂點**。現在，如果某個圖 $H$ 包含 $TG$ 作為子圖，那麼 $H$ 被稱為具有 $G$ 作為 **拓撲小圖**。

給定一個圖 $G$ ，以及另一個圖 $G'$ ， $G'$ 被稱為一個 $IG$ ，如果 $G'$ 是由 $G$ 透過用連通圖替換 $G$ 的頂點形成的，使得如果一個頂點 $v$ 被一個連通圖 $G_{v}$ 替換，則存在連線 $G_{v}$ 到替換 $v$ 在 $G$ 中相鄰的頂點的每個圖的邊，並且僅限於那些圖。這個過程稱為 **膨脹**，因此用一個 $I$ 來表示它，而替換 $G$ 中頂點的圖被稱為 $G'$ 的 **分支集**。現在，如果某個圖 $H$ 包含一個 $IG$ 作為子圖，那麼 $H$ 被認為具有 $G$ 作為 **次要圖**，記為 $G\preceq H$ 。

定理：如果 $G$ 是 $H$ 的拓撲次要圖，那麼 $G\preceq H$ 。

證明：由於 $G$ 是 $H$ 的拓撲次圖，因此存在 $TG$ 是 $H$ 的子圖。將該 $TG$ 稱為 $G'$ 。將 $G'$ 的分支頂點從 $1$ 到 $|G|$ 編號。現在，對於 $G'$ 中的每個細分頂點 $v$ ，將 $v$ 新增到包含距離 $v$ 最小的分支頂點的分支集中。如果 $v$ 具有兩個距離最小的分支頂點，則將其新增到包含編號較小的分支頂點的分支集中。現在，每個頂點都在一個分支集中，並且分支集是不相交的，並且每個分支集都是連通的。這產生了 $IG$ 是 $H$ 的子圖，因此 $G\preceq H$ 。

關聯、鄰接、度

關聯的概念將邊與由該邊連線的節點相關聯。例如，邊 $\left\{u,v\right\}$ 與節點 $u$ 和 $v$ 關聯。

如果一條邊連線了兩個節點，我們就說這兩個節點是相鄰的。更正式地說， $u,v\in V(G)$ 如果 $\left\{u,v\right\}\in E(G)$ 相鄰。節點 v 的鄰域，記為 $N(v)$ ，是所有與它相鄰的節點的集合。

節點 v 的度，記為 $\deg(v)$ ，是與它關聯的邊的數量。在一個有向圖中，入度和出度分別計算進入和離開頂點的有向邊的數量。

圖 $G$ 的最小度，記為 $\delta (G)$ ，是 $\min \limits _{v\in V(G)}d(v)$ ，即 $G$ 中所有頂點的度數的最小值。

類似地，圖 $G$ 的最大度，記為 $\Delta (G)$ ，是 $\max \limits _{v\in V(G)}d(v)$ ，即 $G$ 中所有頂點的度數的最大值。

握手引理

握手引理是度數和公式（有時也稱為握手引理）的結果，

\sum _{v\in V}\deg(v)=2|E|

證明尤拉證明度數和公式使用了雙重計數技巧：他用兩種不同的方法計算了關聯對 $\left\{v,e\right\}$ 的數量，其中e是邊，頂點v是它的一個端點。頂點v屬於 deg(v) 個對，其中 deg(v)（v 的度數）是與它關聯的邊的數量。因此，關聯對的數量是度數的總和。然而，圖中的每條邊都屬於正好兩個關聯對，一個對應它的每個端點；因此，關聯對的數量是 2|E|。由於這兩個公式計算的是同一組物件，因此它們的值必須相等。

在整數的和中，和的奇偶性不受和中偶數項的影響；當奇數項的數量為偶數時，總和為偶數；當奇數項的數量為奇數時，總和為奇數。由於度數和公式的一側是偶數 2|E|，因此另一側的和必須包含偶數個奇數項；也就是說，必須存在偶數個奇度頂點。

曼特爾定理

一個n個頂點的無三角形圖中邊的最大數量是 $\lfloor n^{2}/4\rfloor .$

證明

假設 $G(V,E)$ 是一個有 $n$ 個頂點的圖。我們來算一下這個圖最多可以有多少條邊。

對於每條邊 $\left\{u,v\right\}$ ，如果存在一個與 $u$ 和 $v$ 都相鄰的頂點 $w$ ，那麼就會形成一個三角形。因此我們知道這樣的頂點不存在，也就是說 $u$ 的鄰域與 $v$ 的鄰域不相交。

$N(v)\cap N(u)=\emptyset$

這意味著任何其他頂點要麼與 $u$ 相鄰，要麼與 $v$ 相鄰。當我們計算 $u$ 和 $v$ 的度數時，我們發現它們的和最多為 $n$ ，因為一個頂點要麼被計入 $u$ 的鄰域，要麼被計入 $v$ 的鄰域。

$d(u)+d(v)<n$

上面的不等式對於每條邊都成立。因此我們有與邊數一樣多的不等式。如果我們將所有這些不等式加起來，我們會發現每個頂點的度數 $d(v)$ 會出現 $d(v)$ 次，所以我們必須加上 $d(v)^{2}$ 。不等式變為

$\sum _{v\in V(G)}d(v)^{2}<n\cdot |E(G)|$

因為每條邊都有兩個端點，所以所有頂點的度數之和恰好是邊數的兩倍。

$\sum _{v\in V(G)}d(v)=2\cdot |E(G)|$

在具有標準內積的 $\mathbb {R} ^{n}$ 中，柯西-施瓦茨不等式為

$\left(\sum _{i=1}^{n}x_{i}y_{i}\right)^{2}\leq \left(\sum _{i=1}^{n}x_{i}^{2}\right)\left(\sum _{i=1}^{n}y_{i}^{2}\right).$

上面兩個公式推匯出

$\left(2\cdot |E(G)|\right)^{2}=\left(\sum _{v\in V(G)}d(v)\cdot 1\right)^{2}\leq n\cdot \sum _{v\in V(G)}d(v)^{2}\leq n\cdot (n\cdot |E(G)|)$

解出 $|E(G)|$ ，得到

$|E(G)|\leq n^{2}/4$

遍歷

在研究圖時，我們經常需要知道從一個頂點到另一個頂點的各種路徑，以及這些路徑的不同型別。為了理解遍歷的概念，我們可以想象圖中的節點是城市裡的方塊，邊是連線這些方塊的道路。假設你必須從一個方塊步行到另一個方塊，並且在你的目的地之間有一些中間方塊。你可以寫下所有你必須經過的道路的列表，路徑的概念就是對這個直觀概念的正式化。

路徑、閉路徑、迴路和圈

一個 *u-v* **路徑** 定義為一個從 *u* 開始到 *v* 結束的頂點序列，其中序列中連續的頂點是圖中相鄰的頂點。
一個帶標籤的圖形在 6 個頂點和 7 個邊上的繪製。
- 一個 **閉路徑** 是一個路徑，其中第一個和最後一個頂點相同。
一個 *u-v* **跡** 是一個 *u-v* 路徑，其中沒有邊被重複（每條邊最多使用一次）。
- 一個 **迴路** 或者 **閉跡** 是一個跡，其中第一個和最後一個頂點相同。
一個 *u-v* **通路** 是一個 *u-v* 路徑，其中沒有頂點被重複（每個頂點最多使用一次）。
- 一個 **圈** 是一個閉合通路，其中第一個和最後一個頂點相同。

例如，在右邊的圖中， $(6,4,5,1)$ 是一個行走。而 $(4,5,2,3,4)$ 和 $(1,5,2,1)$ 是迴圈。

圖中的距離

現在，我們需要在圖中定義一個距離的概念；這有助於我們在圖中編碼更多資料。

行走的長度: 在特定行走中使用的邊的數量。

如果一條邊被使用多次，那麼它就被計算多次。
平凡行走是長度為 0 的行走。

定理

如果圖G包含一個長度為 $\ell$ 的 u-v 行走，那麼G包含一個長度 ≤ $\ell$ 的 u-v 路徑。

證明

令P是長度最短的u-v行走。我們斷言P是一條路徑（因為是最短的，所以它消除了重複的頂點）。

假設不是。假設P不是一條路徑。然後，至少有一個頂點被重複（使用兩次）。然後，設定

P:u=u_{0},u_{1},\ldots ,u_{\ell }=v

，其中

\ell

是P的長度。

並且，我們知道

u_{i}=u_{j}

對於某些

0\leq i<j\leq \ell

。

然後，刪除重複的頂點(頂點)得到

P':u=u_{0},u_{1},\ldots ,u_{i},u_{j+1},\ldots ,u_{\ell }=v

。但是，然後我們得到P'的長度小於P的長度，這與我們假設P是最短長度的行走相矛盾。

所以，P必須是一條路徑，而且它比任何其他在P中具有頂點的行走都要短。

因此，存在一個長度最多為

\ell

的u-v路徑。

圖距離

兩個頂點 $u$ 和 $v$ 之間的圖距離 $d(u,v)$ 是連線它們的路徑的最小長度。也是圖測地線的長度。
圖中兩個頂點 $(u,v)$ 之間最短的路徑被稱為測地線。
如果不存在這樣的路徑（如果頂點位於不同的連通分量中），則距離設定為 $\infty$ .

測地線

對於圖G中的任意兩個頂點u和v，u和v之間的距離定義為u和v之間最短路徑的長度，記為d(u,v)。

長度為d(u,v)的路徑被稱為測地線。

d(u,v)的性質：
對於測地線P:u=u₀u₁u₂...u_k=v和一些0≤i,j≤k

d(u₀u_k) = k
d(u_iu_i) = 0（沒有移動）
d(u₀u_i) = i
d(u_iu_j) = |j-i|

連通性

是否可以從圖中的一個頂點遍歷到另一個頂點，取決於圖的連通性。

連通性的定義

如果在G中存在一條u-v路徑，那麼我們說u和v是連通的
如果在G中對於每一對頂點u和v都存在一條u-v路徑，那麼我們說G是連通的

關於連通性的定理

定理：設G是一個至少有3個頂點的圖。如果在G中存在不同的頂點u和v，使得G-u和G-v都是連通的，那麼G也是連通的。

證明：設w是G中的一個頂點，它不同於u和v。我們要證明連通性，即對於G中每對頂點（x,y），在G中存在一條x-y路徑。我們可以考慮三種（部分重疊）情況

如果x和y都不是u，那麼在G-u中存在一條x-y路徑，這在G中也是一條x-y路徑。
如果x和y都不是v，那麼在G-v中存在一條x-y路徑，這在G中也是一條x-y路徑。
如果{x,y} = {u,v}，那麼根據前兩種情況我們可以看到，存在一條u-w路徑和一條w-v路徑。將它們組合起來就得到一條u-v路徑。

頂點和邊連通性

如果對於圖 *G* 中的任意一個子集 $S\subseteq V(G)$ ，只要 $|S|<k$ ， $G-S$ 仍然連通，並且 $|G|>k$ ，那麼稱圖 *G* 為 *k* 連通圖。

類似地，如果對於圖 *G* 中的任意一個子集 $S\subseteq E(G)$ ，只要 $|S|<\ell$ ， $G-S$ 仍然連通，並且 $|G|>1$ ，那麼稱圖 *G* 為 $\ell$ 邊連通。

*G* 的**連通度**是使 *G* 為 *k* 連通的最大的 *k*，記作 $\kappa (G)$ 。

類似地，*G* 的**邊連通度**是使 *G* 為 $\ell$ 邊連通的最大的 $\ell$ ，記作 $\lambda (G)$ 。

連通度定理

定理： 設 *G* 是一個 *k* 連通圖，那麼對於任意自然數 $\forall i\in \mathbb {N} ,0\leq i\leq k$ ，*G* 都是 *i* 連通的。

證明： 因為 *G* 是 *k* 連通的，所以對於所有子集 $S\subseteq V(G),|S|<k$ ， $G-S$ 是連通的。由於 $i\leq k$ ，因此對於所有子集 $S\subseteq V(G),|S|<i\leq k$ ， $G-S$ 也是連通的。

定理： 令G為非平凡圖。則， $\lambda (G)\leq \delta (G)$ .

證明： 取G中度數為 $\delta (G)$ 的頂點v。然後，移除G中與v關聯的所有邊將v與圖的其餘部分分離，前提是 $|G|>\delta (G)+1$ 。因此，G不能是 $\delta (G)$ 邊連通的，因此 $\lambda (G)\leq \delta (G)$ .

練習：連通性

如果G是 $\ell$ 邊連通的，證明G也是i邊連通的 $\forall i\in \mathbb {N} ,0\leq i\leq \ell$ .

同構

圖G和H的同構是G和H的頂點集之間的雙射

f\colon V(G)\to V(H)\,\!

使得G中的任意兩個頂點u和v在G中相鄰當且僅當ƒ(u)和ƒ(v)在H中相鄰。這種雙射通常被稱為“邊保持雙射”，這與同構的一般概念是保持結構的雙射相一致。

在上述定義中，圖被理解為無向非標記非加權圖。然而，同構的概念可以應用於圖概念的所有其他變體，方法是新增保持相應結構元素的要求：弧方向、邊權重等，但以下情況除外。當談論具有唯一標籤的圖標籤時，通常從整數範圍 1,...,n 中獲取，其中n 是圖的頂點數，兩個標記圖被稱為同構，如果對應的底層未標記圖是同構的。

如果兩個圖之間存在同構，那麼這兩個圖被稱為同構，我們寫 $G\simeq H$ 。在雙射是圖到自身的對映的情況下，即當G和H是同一個圖時，雙射被稱為G的自同構。

圖同構是圖上的等價關係，因此它將所有圖的類劃分為等價類。一組相互同構的圖被稱為圖同構類。

示例

下面顯示的兩個圖是同構的，儘管它們的繪製方式不同。

圖 G	圖 H	同構 G 和 H 之間
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

動機

“同構”的正式概念，例如“圖同構”，捕捉了非正式的概念，即一些物件具有“相同的結構”，如果忽略所討論物件的“原子”元件的個體區別，請參見上面的示例。每當“原子”元件（對於圖，頂點和邊）的個體性對於正確表示由圖建模的內容很重要時，模型會透過對結構施加額外的限制來改進，並且使用其他數學物件：有向圖、標記圖、彩色圖、有根樹等等。同構關係也可以針對所有這些圖的概括來定義：同構雙射必須保留定義所討論的物件型別的結構元素：弧、標籤、頂點/邊顏色、有根樹的根等等。

“圖同構”的概念使我們能夠區分圖本身的結構固有的圖屬性與與圖表示相關的屬性：圖繪製、圖資料結構、圖標籤等等。例如，如果一個圖只有一個迴圈，那麼它同構類的所有圖也只有一個迴圈。另一方面，在頂點由整數 1、2、... N（表示）的常見情況下，則表示式

\sum _{v\in V(G)}v\cdot {\text{deg }}v

對於兩個同構圖可能不同。

補圖

圖G的補圖或逆圖是一個具有相同頂點的圖H，其中H的兩個頂點相鄰當且僅當它們在G中不相鄰。也就是說，為了生成一個圖的補圖，需要填充所有形成完全圖所需的缺失邊，並刪除之前存在的邊。然而，它並不是圖的集合補；只有邊被補充了。

正式構造

圖 $G=(V,E)$ 的補圖是圖 ${\bar {G}}=(V,E')$ ，使得對於所有頂點對 $u,v\in G$ ，存在邊 $(u,v)\in E'$ 當且僅當 $(u,v)\not \in E$ 。如果我們令 $K=V\times V$ ，我們發現 $E'=K\setminus E$ 。

應用和示例

幾個圖論概念透過補圖彼此相關

無邊圖的補圖是完全圖，反之亦然。
任何無三角圖的補圖是無爪圖。
自補圖是與自身補圖同構的圖。
互補圖的定義是可以透過不相交併集和補運算構建的圖，它們構成一個自補圖族：任何互補圖的補圖是另一個（可能不同的）互補圖。

樹

樹是一種連通圖。有向圖如果連通且無環，則為樹。無向圖如果連通，有 $|V|-1$ 條邊，且無環（滿足其中兩個性質的圖也滿足所有三個性質）。

練習：等價定義

證明以下是對樹的等價定義

具有最小邊數且連通的圖。
具有最大邊數且無環的圖。
無環，新增任何邊都會產生環的圖。
具有 n 個節點和 n-1 條邊且連通的圖。
任何兩個節點都透過唯一路徑連線的圖（路徑邊只能遍歷一次）。

提示：為了使總證明簡短，以合適的順序排列定義，然後證明 A=>B=>C=>D=>E=>A。對具有零個和一個節點的圖要特別小心。

有根樹

如果一個頂點被指定為根，則樹被稱為有根樹，在這種情況下，邊具有自然的定向，朝向或遠離根。樹序是樹頂點的偏序關係，其中u ≤ v 當且僅當從根到v 的唯一路徑經過u。如果某個圖G 的子圖是有根樹，並且G 中的每條邊的端點在該樹序中都是可比較的，那麼這個有根樹就是正常樹。

在有根樹中，頂點的父節點是連線到它的通往根的路徑上的頂點；除根之外的每個頂點都只有一個父節點。頂點v 的子節點是指以v 為父節點的頂點。

在有根樹中，所有頂點最多隻有一個父節點。

完全圖

完全圖是指所有頂點對都由邊連線的圖。具有 $n$ 個頂點的完全圖表示為 $K_{n}$ 。

任何包含與 $K_{5}$ 同構的子圖的圖都是非平面的。

練習：平面性

$K_{5}$ 可以畫在環面上嗎？
$K_{5}$ 可以畫在克萊因瓶的表面上嗎？

練習：子圖和同構

在 $K_{n+1}$ 中包含了多少個不同的 $K_{n}$ 的副本？
$K_{n}$ 有多少個自同構？

二部圖

如果圖 $G=(V,E)$ 的頂點集 $V$ 可以被劃分為兩個不相交的子集，使得對於每條邊 $(u,v)\in E$ ， $u$ 和 $v$ 位於相反的子集中，那麼這個圖就是二部圖。

此外，一個圖是二部圖當且僅當它不包含奇環。

證明

設

G=(V,E)

是一個任意的、固定的圖，它包含一個奇環。

$G$ 是二部圖 $\Longrightarrow G$ 不包含奇環

為了反證法，假設

G

包含一個奇環。

設

G_{1},G_{2}

是兩個不相交的子集，它們在

G

上形成二部劃分。

選擇一個奇數環

C

在

G

中，並且，不失一般性地，選擇一個節點

v_{1}\in C

來自

G_{1}

。從

v_{1}

開始遍歷

C

，注意根據二分圖的定義，每個節點都在與它的鄰居不同的子集中

G_{1},G_{2}

。

遍歷的最後一個節點，

v_{n}

，必須在

G_{1}

中，因為

C

是一個奇數環。然而，

v_{n}

與

v_{1}

相鄰，根據環的定義，這與

G_{1}

包含兩個相鄰節點相矛盾，所以

G

不能包含奇數環。

由於我們已經查看了任意的

C

，並且不失一般性地從

G_{1}

中選擇了

v

，我們已經證明了蘊含關係。

$G$ 不包含奇數環 $\Longrightarrow G$ 是二分圖

我們提供一個演算法將節點排序成兩個不相交的集合。

固定一個任意節點 $v\in V$ 。
對於圖中的每個節點 $x$ ，計算從 $x$ 到 $v$ 的最短路徑。
設 $A,B$ 為節點集合，使得從 $x$ 到 $v$ 的最短路徑分別為偶數和奇數。

為了證明該演算法的正確性，我們不妨僅考慮集合

A

。

假設存在兩個相鄰的節點

v_{1},v_{2}\in A

。設

P_{1},P_{2}

分別表示從

v

到

v_{1},v_{2}

的最短路徑。

如果 $P_{1}$ 和 $P_{2}$ 不相交，則 $P_{1},(v_{1},v_{2}),P_{2}$ 構成一個奇數長度的環，因為 $P_{1}$ 和 $P_{2}$ 顯然具有相同的奇偶性，這與假設矛盾。
如果 $P_{1}$ 和 $P_{2}$ 相交，我們選擇與 $v_{1}$ 最近的交點 $v'$ 。注意 $v'$ 不能是 $v_{1}$ 或 $v_{2}$ ，因為從 $v_{1}$ 到 $v_{2}$ 的最短路徑不會有相同的奇偶校驗。觀察到 $v'$ 到 $v_{1}$ 和 $v_{2}$ 的距離必須相同，否則到 $v_{1},v_{2}$ 的最短路徑將穿過另一個節點。然而，這是一個矛盾，因為 $(v',v_{1}),(v_{1},v_{2}),(v',v_{2})$ 將是一個奇數環。

因此，

A

中的任何兩個節點都不能相鄰，並且由於我們無損一般性地考慮了

A

，我們已經證明了演算法的正確性，因此反向蘊涵也成立。

完全二部圖

完整二分圖 $K_{m,n}$ 是一個圖，它由兩個不相交的子集 $A,B$ 組成，它們的基數分別為 $m,n$ ，使得 $K_{m,n}$ 包含 $A$ 中每個節點和 $B$ 中每個節點之間的邊。

圖論/定義