图表

(i) 对于$L$中的任何$\alpha$，图$\Gamma_\alpha$是连通的。 (ii) 如果$\Gamma' = (A', S')$是$\Gamma$的连通子图，则$L$中存在$\alpha$，使得$\Gamma' \subset \Gamma_\alpha$。 (iii) 如果$\alpha \neq \beta$，则$S_\alpha$中的任何元素都不会在$\Gamma$中与$S_\beta$中的任何元素相连接（等效地，$\Gamma$的每条边都是$\Gamma_\alpha$之一的边）。 (iv) 令$(S'_\lambda)_{\lambda \in M}$为$S$的划分，这样，如果$\lambda \neq \mu$，$S'_\lambda$中没有元素加入$\Gamma$与$S'_\mu$的任何元素；那么每个集合$S'_\lambda$都是$\Gamma$的连通分量的并。

(i) 设$\alpha$在$L$中，并且$a$和$b$在$S_\alpha$中。那么$\Gamma$中存在一条连接$a$和$b$的路径$c = (x_0, \ldots, x_n)$。对于任何带有$0 \leq i \leq n$的$i$，路径$(x_0, \ldots, x_i)$在$\Gamma$中将$a$连接到$x_i$，因此$x_i \in S_\alpha$。因此，$c$是$\Gamma_\alpha$*中*连接$a$和$b$的路径。由此可知$\Gamma_\alpha$是连通的。

(ii) 令$\Gamma' = (A', S')$为$\Gamma$的非空连通子图，令$a$为$S'$的元素，令$S_\alpha$为$S$包含$a$的连通分量。对于$S'$中的任何$b$，存在连接$\Gamma'$中的$a$和$b$的路径$c$，以及$\Gamma$中的*更不必说*。由此可知$S' \subset S_\alpha$。

(iii) 给定$L$的不同元素、$\alpha$和$\beta$，以及顶点$a \in S_\alpha$和$b \in S_\beta$，没有连接$a$和$b$的路径，特别是没有连接$a$和的边$b$。

(iv) 令$a$在$S'_\lambda$中，并令$S_\alpha$为$\Gamma$包含$a$的连通分量。那么，对于$S_\alpha$中的任何$b$，都存在一条连接$\Gamma$中的$a$和$b$的路径$(x_0, \ldots, x_n)$。如果 $i$ 是整数，使得 $0 \leq i < n$ 并且如果 $x_i \in S'_\lambda$，则从 $x_i$ 开始将 $x_{i+1} \in S'_\lambda$ 连接到 $x_{i+1}$。接下来是归纳，$x_i \in S'_\lambda$代表$0 \leq i \leq n$，特别是$b = x_n$在$S'_\lambda$中。因此，$S_\alpha \subset S'_\lambda$。

假设 $\Gamma$ 未连通，并令 $S'$ 为其连通分量之一。根据命题 1 (i)，集合 $S'' = S - S'$ 是非空的，并且根据命题 1 (iii)，$S'$ 中的任何元素都不会与 $S''$ 中的任何元素连接。

现在假设 $\Gamma$ 已连接，并令 $(S', S'')$ 为划分与指定的性质。根据命题 1 (iv)，集合 $S'$ 包含至少有一个连通分量，因此 $S' = S$ 和 $S'' = \varnothing$ 是矛盾的。

根据命题 1 (iv)，条件是充分的。根据提案 1 (iii)，这是必要的。

(i) 如果 $\Gamma$ 至少有一个顶点，则它有一个终端顶点。 (ii) 如果$\Gamma$至少有两个顶点，则其集合顶点中有划分$(S', S'')$分成两个非空子集，使得两个不同的顶点都属于到$S'$或都属于到$S''$ 从未加入。

假设$\Gamma$至少有一个顶点，并令$(x_0, \ldots, x_n)$为$\Gamma$中最大长度的单射路径。顶点$x_0$不能连接到与$x_0, x_1, \ldots, x_n$不同的顶点$y$，否则$\Gamma$中将存在长度$n + 1$的单射路径，即$(y, x_0, \ldots, x_n)$。顶点 $x_0$ 不与任何带有 $2 \leq i \leq n$ 的顶点 $x_i$ 连接，否则 $(x_0, x_1, \ldots, x_i)$ 将成为森林 $\Gamma$ 中的环路。因此，$x_0$是终结符。

我们将通过$\Gamma$顶点的数$m$的归纳来证明（ii），情况$m = 2$是平凡的。假设对于具有 $m - 1$ 顶点的图证明了 $m \geq 3$ 和断言 (ii)。令 $a$ 为$\Gamma$ (cf. (i)) 的终端顶点。我们将归纳假设应用于$\Gamma$的完整子图，其顶点是$\Gamma$的顶点$x \neq a$。因此，$S$与$S'_1 \cup S''_1 = S - \{a\}$存在两个非空不相交的子集$S'_1$和$S''_1$，并且$S'_1$（或$S''_1$）中的两个不同顶点永远不会连接。由于$a$最多连接到$\Gamma$的一个顶点，因此我们可以假设例没有连接到$S'_1$中的任何顶点。 划分 $(S'_1, S''_1 \cup \{a\})$ 则具有所需的性质。 Q.E.D.

对于任何整数 $n \geq 1$，用 $A_n$ 表示顶点为整数 $1, 2, \ldots, n$ 且边为对 $\{i, j\}$ 和 $i - j = \pm 1$ 的图：

如果图$\Gamma$与$A_{m+1}$同构的，则称其为长度$m \geq 0$的链。这相当于$\Gamma$中存在单射路径$(x_0, \ldots, x_m)$包含所有顶点，如果$|i - j| > 1$则顶点$x_i$和$x_j$不被连接。

假设图$\Gamma$是一个链$(x_0, \ldots, x_m)$，具有命题3中列出的属性之前叙述。显然，$\Gamma$的任何顶点最多连接到两个顶点。如果从路径$(x_0, \ldots, x_m)$提取的$i < j$路径$(x_i, \ldots, x_j)$将$x_i$连接到$x_j$；因此，$\Gamma$是相连的。最后，令$(x_{p_1}, \ldots, x_{p_n})$为$\Gamma$中的电路，并令$p_k$为不同整数$p_1, \ldots, p_n$的最小的。存在不同的指标、$i$和$j$，使得$x_{p_k}$连接到$x_{p_i}$和$x_{p_j}$：这是从电路的定义得出的。由于$p_k < p_i$和$p_k < p_j$，我们必然有$p_i = p_j = p_k + 1$，这是一个矛盾，因为$p_1, \ldots, p_n$是不同的。因此，$\Gamma$中没有电路。

相反，令$\Gamma$为一棵没有分支点且具有有限非零数顶点的树，并令$(x_0, \ldots, x_m)$为$\Gamma$中最大长度的单射路径。 $x_0, \ldots, x_m$以外的顶点用$T$集合表示。顶点 $b \in T$ 不能连接到任何顶点 $x_i$，因为我们可以有

a) $i = 0$，但是$(b, x_0, \ldots, x_m)$将是$\Gamma$中长度$m + 1$的单射路径，或者 b) $i = m$，但是$(x_0, \ldots, x_m, b)$将是$\Gamma$中长度$m + 1$的单射路径，或者 c) $0 < i < m$，但是$x_i$将连接到三个不同的顶点$x_{i-1}$、$x_{i+1}$和$b$。

由于 $\Gamma$ 已连通，因此 $T$ 被 Cor 为空。命题1的1.此外，如果有$i, j$与$j - i > 1$和$x_i, x_j$连接，则$\Gamma$中将存在$(x_i, x_{i+1}, \ldots, x_j)$电路。因此，$\Gamma$是一条链。 Q.E.D.