图的基本概念

图的基础知识¶

图的定义¶

一个图 $G$ 定义为一个有序对 ( V , E )，记为 G = ( V , E )，其中：

V 是一个非空集合，称为顶点集或边集，其元素称为项点或点
E 是由 V 中的点组成的无序点对构成的集合，称为边集，其元素称为边，且同一点对在 E 中可出现多次。

图 $G$ 的顶点集也记为V(G)，边集也记为E(G)。

顶点集和边集都有限的图称为有限图。

只有一个项点而无边的图称为平凡图。其他所有的图都称为非平凡图。

Info

做题往往需要先排除平凡图

边集为空的图称为空图。

图 $G$ 的顶点数 (或阶数) 和边数可分别用符号 n(G) 和 m(G) 表示。

连接两个相同顶点的边的条数，叫做边的重数。重数大于 1 的边称为重边。

端点重合为一点的边称为环。

既没有环也没有重边的图称为简单图。其他所有的图都称为复合图。

边记为 uv，也可记 uv 为 e ，即 e = uv。此时称 u 和 v 是 e 的端点，并称 u 和 v 相邻，u (或 v) 与 e 相关联。

若两条边有一个共同的端点，则称这两条边相邻。

若用小圆点代表点，连线代表边，则可将一个图用“图形” 来表示。

图的同构¶

设有两个图 G₁ = (V₁ , E₁ )和 G₂ = (V₂ , E₂ )，若在其项点集合之间存在双射，即存在一一对应的关系，使得边之间有如下的关系:

设 u_{1} \Leftrightarrow u_{2}, v_{1} \Leftrightarrow v_{2}, u_{1}, v_{1} \in V_{1}, u_{2}, v_{2} \in V_{2} u_{1} v_{1} \in E_{1} \Leftrightarrow u_{2} v_{2} \in E_{2}

u_{1} v_{1} 重 数 = u_{2} v_{2} 重 数

则称两图 G₁ , G₂ 同构，记为：

G_{1} ≅ G_{2}

Abstract

同构关系就是一种等价关系，形成等价类

完全图¶

每两个不同的顶点之问都有一条边相连的简单图称为完全图。

Abstract

完全图是简单图的上限，空图则是下限

在同构意义下，n 个顶点的完全图只有一个，记为 K_n ，也叫 n 阶完全图。

所谓具有二分类 (X, Y) 的偶图(或二部图)是指：一个图，它的点集可以分解为两个(非空)子集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在 Y 中。

完全偶图是指具有二分类 (X , Y) 的简单偶图，其中 X 的每个项点与 Y 的每个项点相连，若 |X|=m ，|Y|=n ，则这样的偶图记为 K_m,n。

补图¶

对于一个简单图 G= (V, E)，令集合

E_{1} = {u v | u \neq v, u, v \in V}

则图 $H = (V E / E_{1})$ 称为 $G$ 的补图，记为：

H = \overset{―}{G} = (V, E / E_{1})

如果一个图和自己的补图是同构的，则称这个图是自补的，并记为：

G ≅ \overset{―}{G}

自补图性质¶

若 n 阶图 $G$ 是自补的 ( 即 $G ≅ \overset{―}{G}$ )，则 $n = 0, 1 (\mod 4)$ 。

正则图¶

G 的顶点的度 d (v) 是指 $G$ 中与 v 关联的边的数目，每个环计算两次。

用 $δ (G)$ 和 $Δ (G)$ 分别表示 G 的项点的最小度和最大度。

为方便，奇数度的顶点称为奇点，偶数度的顶点称偶点。

设 G = (V，E) 为简单图，如果对所有 $v \in V$ ，有 d(v) = k ，称图 $G$ 为k-正则图。

完全图 K_n 和完全偶图 K_n,m 均是正则图。

握手定理¶

图 G = (V , E ) 中所有项点的度的和等于边数 m 的 2 倍，即

\sum_{v \in V} d (v) = 2 m

Abstract

也叫：握手定理，图论第一定理

推论 1¶

在任何图中，奇点个数为偶数。

推论 2¶

正则图的阶数和度数不同时为奇数。

推论 3¶

由握手定理有：

n δ < \sum_{v \in V (G)} d (v) = 2 m \leq n Δ δ \leq \frac{2 m}{n} \leq Δ

可图数组¶

一个图 $G$ 的各个点的度 $d_{1}, d_{2}, \dots, d_{n}$ 构成的非负整数组 $(d_{1}, d_{2}, \dots, d_{n})$ 称为 $G$ 的 度序列。

度序列通常以度数非递增的顺序列出？

若对一个非负整数组 $(d_{1}, d_{2}, \dots, d_{n})$ 满足 $\exists m \in Z, \sum_{i = 1}^{n} d_{i} = 2 m$ (数组和为偶数)，存在一个简单图 $G$ 以该数组为度序列，则称这个数组是可图的，也叫这个数组为图数组/图序列。

Abstract

关于图序列我们研究三个问题：

存在问题——什么样的数组是图序列
计数问题——一个图序列对应多少个不同构的图
唯一性问题——怎样的图序列对应唯一一个同构的图

必要条件¶

非负整数组 $(d_{1}, d_{2}, \dots, d_{n})$ 是图序列的一个必要条件是：

\sum_{i = 1}^{n} d_{i} 是偶数，或者： 2 | \sum_{i = 1}^{n} d_{i}

另一个必要条件是：（可简单图化）

d_{i} \leq n - 1

图序列相关定理¶

Havel-Hakimi ¶

设有非负整数组 $Π = (d_{1}, d_{2}, \dots, d_{n})$ ，且 $\sum_{i = 1}^{n} d_{i}$ 是一个偶数， $n - 1 \geq d_{1} \geq d_{2} \geq \dots \geq d_{n}$ ， $Π$ 是可图（可简单图化）的充要条件为：

Π^{'} = (d_{2} - 1, d_{3} - 1, \dots, d_{d_{1} + 1} - 1, d_{d_{1} + 2}, \dots, d_{n})

是可图的（是图序列）。

对任意一个序列，判断是否可图的步骤如下：（当然先确保满足可图的必要条件）

按递减排序
去掉第一个元素 $d_{1}$ ，后面 $d_{1}$ 个元素依次减 1️⃣（ $- 1$ ）
重复前面两个步骤，直到：
只剩一个点，则该序列是可图的，即是图序列
减 1️⃣ 后出现负数，则该序列是不可图的，即不是图序列

中证明充分性：¶

情形 1¶

点 $v_{1}$ 与点 $v_{2}, v_{3}, \dots, v_{d + 1}$ 邻接

则 $G - v_{1}$ 的度序列正好 $Π_{1}$

情形 2¶

点 $v_{1}$ 与点 $v_{2}, v_{3}, \dots, v_{d + 1}$ 的某些顶点邻接

作如下假设：

设 $v_{1}$ 与 $v_{j_{0}}$ 邻接，但当 $k > j_{0}$ 时， $v_{1}$ 与 $v_{k}$ 不邻接；
设 $v_{1}$ 与 $v_{i_{0}}$ 不邻接，但当 $k < i_{0}$ 时， $v_{1}$ 与 $v_{k}$ 邻接；

进行这样的操作：

去掉边 $v_{1} v_{j_{0}}$ 和 $v_{i_{0}} v_{m}$
加上边 $v_{j_{0}} v_{m}$ 和 $v_{1} v_{i_{0}}$

显然新图与原来的度序列相同，但是，但 $j_{0}$ 减小了， $i_{0}$ 增大了！

如此循环下去， $j_{0} = i_{0}$ 时情形 2 就可以变成情形 1

厄多斯定理¶

非负整数组：

π = (d_{1}, d_{2}, \dots, d_{n}), d_{1} \geq d_{2} \geq d_{n}, \sum_{i = 1}^{n} d_{i} = 2 m

是图序列的充分必要条件是：

\sum_{i = 1}^{r} d_{i} \leq r (r - 1) + \sum_{i = r + 1}^{n} min {r, d_{i}}, 1 \leq r \leq n - 1

Warning

证明非常困难捏

定理？¶

一个满足 $d_{2} = d_{n - 1}$ 的图序列 $π = (d_{1}, d_{2}, \dots, d_{n})$ 是唯一图序列的充分必要条件时下列条件之一满足：

$d_{1} = d_{n}, d_{n} \in {1, n - 1, n - 2}$ ；
$d_{1} = d_{n} = 2, n = 5$ ；
$d_{1} > d_{2} = d_{n} = 1$ ；
$d_{1} > d_{2} = d_{n} = 2, d_{1} \in {n - 1, n - 2}$ ；
$n - 2 = d_{1} = d_{n - 1} > d_{n}$ ；
$n - 3 = d_{1} = d_{n - 1} > d_{n} = 1$ ；
$n - 1 = d_{1} > d_{2} = d_{n} = 3, n = 6$ ；

定理-简单图度数不可能互不相同¶

一个简单图 $G$ 的 $n$ 个点的度不能互不相同

证明：因为图 G 为简单图，所以： $Δ (G) \leq n - 1$ 。

情形 1：若 $G$ 没有孤立点，则 $1 \leq d (v) \leq n - 1, \forall v \in V (G)$ , 由鸽笼原理：必有两顶点度数相同；

情形 2：若 $G$ 只有一个孤立点，设 $G_{1}$ 表示 G 去掉孤立点后的部分，则：

1 \leq d (v) \leq n - 2, \forall v \in V (G_{1})

由鸽笼原理：在 $G_{1}$ 里必有两顶点度数相同；

情形 3：若 $G$ 只有两个以上的孤立点，则定理显然成立。

频序列¶

设 $n$ 阶图 $G$ 的各点的度取了 $s$ 个不同的非负整数 $d_{1}, d_{2}, \dots, d_{s}$ 。又设度为 $d_{i}$ 的点有 $b_{i}$ 个 ( $i = 1, 2, \dots, s)$ , 则有 $\sum_{i = 1}^{s} b_{i} = n$ 。故非负整数组 ( $d_{1}, d_{2}, \dots, d_{s}$ ) 是 $n$ 的一个划分，称为 $G$ 的频序列

性质¶

一个 $n$ 阶图 $G$ 和它的补图有相同的频序列

拓扑不变量¶

图 $G$ 的拓扑不变量是指与图 $G$ 有关的一个数或数组(向量)。它对于与图 $G$ 同构的所有图来说，不会发生改变。

一个图 $G$ 可以对应很多拓扑不变量。如果某组不变量可完全决定一个图，称它为不变量的完全集。

图的运算¶

子图和真子图¶

如果 $V (H) \subseteq V (G), E (H) \subseteq E (G)$ ，且 $H$ 中边的重数不超过 $G$ 中对应边的重数，则称 $H$ 是 $G$ 的子图，记为 $H \subseteq G$ 。有时又称 $G$ 是 $H$ 的母图。

当 $H \subseteq G$ ，但 $H \neq G$ 时，则记为 $H \subset G$ ，且称 $H$ 为 $G$ 的真子图。

生成子图¶

$G$ 的生成子图是指满足 $V (H) = V (G)$ 的子图 $H$ 。也就是包含所有顶点但不包含所有边的子图。

计数性质¶

简单图 $G = (n, m)$ 的所有不同的生成子图个数是 $2^{m}$ （包括 $G$ 本身和空图）。

导出子图¶

假设 $V^{'}$ 是 $V$ 的一个非空子集。以 $V^{'}$ 为顶点集，以两端点均在 $V^{'}$ 中的边的全体为边集所组成的子图，称为 $G$ 的由 $V^{'}$ 导出的子图，记为 $G [V^{'}]$ ，简称为 $G$ 的 (点) 导出子图。

假设 $E^{'}$ 是 $E$ 的非空子集。以 $E^{'}$ 为边集，以 $E^{'}$ 中边的端点全体为顶点集所组成的子图称为 $G$ 的由 $E^{'}$ 导出的子图，记为 $G [E^{'}]$ ，简称为 $G$ 的边导出子图 。

删点运算¶

(点) 导出子图 $G [V ∖ V^{'}]$ 记为 $G - V^{'}$ 。它是 $G$ 中删除 $V^{'}$ 中的项点以及与这些项点相关联的边所得到的子图。若 $V^{'} = {v}$ ，则把 $G - {v}$ 简记为 $G - v$ 。

删边运算¶

边集为 $E ∖ E^{'}$ 的 $G$ 的边导出子图简记为 $G - E^{'}$ 。若 $E^{'} = {e}$ ，则把 $G - e$ 简记为 $G - e$ 。

删边运算会删掉那些度数变为 0 的顶点

Abstract

设 $G_{1}$ ， $G_{2}$ 是 $G$ 的子图。若 $G_{1}$ 和 $G_{2}$ 无公共顶点，则称它们是不相交的

若 $G_{1}$ 和 $G_{2}$ 无公共边，则称它们是边不重的

并运算¶

$G_{1}$ 和 $G_{2}$ 的并图 $G_{1} U G_{2}$ 是指 $G$ 的一个子图：

其顶点集为 $V (G_{1}) \cup V (G_{2})$ ；
其边集为 $E (G_{1}) \cup E (G_{2})$ ；

如果 $G_{1}$ 和 $G_{2}$ 是不相交的，有时就记其并图为 $G_{1} + G_{2}$ 。

交运算¶

$G_{1}$ 和 $G_{2}$ 的交图 $G_{1} \cap G_{2}$ ，是指 $G$ 的一个子图：

其顶点集为 $V (G_{1}) \cap V (G_{2})$ ；
其边集为 $E (G_{1}) \cap E (G_{2})$ ；

此时 $G_{1}$ 和 $G_{2}$ 至少要有一个公共顶点！

差运算¶

$G_{1}$ 和 $G_{2}$ 的差 $G_{1} - G_{2}$ 是由 $G_{1}$ 中去掉 $G_{2}$ 中的边组成的图。

Warning

没有去掉那些边的端点！即使剩下 0 度数端点仍要保留！

对称差/环和差¶

$G_{1}$ 和 $G_{2}$ 的对称差 $G_{1} Δ G_{2}$ 是 $G_{1} \cup G_{2}$ 去掉 $G_{1} \cap G_{2}$ 所得到的图，即 :

G_{1} Δ G_{2} = (G_{1} \cup G_{2}) - (G_{1} \cap G_{2}) = (G_{1} - G_{2}) \cup (G_{2} - G_{1})

联运算¶

在不相交的 $G_{1}$ 和 $G_{2}$ 的并图 $G_{1} \cup G_{2}$ 中，把 $G_{1}$ 的每个项点和 $G_{2}$ 的每个项点连接起来所得到的图称为 $G_{1}$ 和 $G_{2}$ 的联图，记为 $G_{1} \lor G_{2}$ 。

Abstract

$u_{i} adj v_{i}$ 表示 $u_{i}$ 和 $v_{i}$ 邻接

(笛卡尔)积运算¶

设 $G_{1} = (V_{1}, E_{1}), G_{2} = (V_{2}, E_{2})$ ，对点集 $V = V_{1} \times V_{2}$ （笛卡尔集）中任意两个点 $u = (u_{1}, u_{2})$ 和 $v = (v_{1}, v_{2})$ ，当以下式子成立时：

(u_{1} = v_{1} \land u_{2} adj v_{2}) \lor (u_{2} = v_{2} \land u_{1} adj v_{1})

就把 $u$ 和 $v$ 连接起来所得到的图 $G$ 称为 $G_{1}$ 和 $G_{2}$ 的积图，记为 $G = G_{1} \times G_{2}$

合成运算¶

設 $G_{i} = (V_{1}, E_{1})$ ， $G_{2} = (V_{2}, E_{2})$ , 对点集 $V = V_{1} \times V_{2}$ （笛卡尔集）中任意两个点 $u = (u_{1}, u_{2})$ 和 $v = (v_{1}, v_{2})$ ，当以下式子成立时：

(u_{1} adj v_{1}) \lor (u_{1} = v_{1} \land u_{2} adj v_{2})

就把 $u$ 和 $v$ 连接起来所得到的图 $G$ 称为 $G_{1}$ 与 $G_{2}$ 的合成图，记为 $G = G_{1} [G_{2}]$

$G_{1} [G_{2}]$ 和 $G_{2} [G_{1}]$ 可能是同构的，也可能是不同构的

Abstract

积运算和合成运算中，得到的点集 $V$ 的定义都是相同的，都是笛卡尔集 $V = V_{1} \times V_{2}$ ；但是边集的定义有所不同

运算	点的数目	边的数目
并 $G_{1} \cup G_{2}$	$n_{1} + n_{2}$	$m_{1} + m_{2}$
联 $G_{1} \lor G_{2}$	$n_{1} + n_{2}$	$m_{1} + m_{2} + n_{1} n_{2}$
积 $G_{1} \times G_{2}$	$n_{1} n_{2}$	$n_{1} m_{2} + n_{2} m_{1}$
合成 $G_{1} [G_{2}]$	$n_{1} n_{2}$	$n_{1} m_{2} + {n_{2}}^{2} m_{1}$

方体¶

一族特别重要的图称为方体，它用积来定义最为自然。

$n$ 方体 $Q_{n}$ 递推地定义为：

$Q_{1} = K_{2}$ ；
$Q_{n} = K_{2} \times Q_{n - 1}$ ；

$Q_{n}$ 有 $2^{n}$ 个点，它的点可以用二进制串 $a_{1} a_{2} \dots a_{n}$ 来标定，其中 $a_{i} \in {0, 1}$ 。

若 $Q_{n}$ 两个点的二进制表示式中只有一位不同，则它们邻接

$2方体$

$3方体$

路与图的连通性¶

途径、迹、路¶

一个有限非空序列:

w = v_{0} e_{1} v_{1} e_{2} v_{2} \dots e_{k} v_{k}

它的项交替地为顶点和边，使得对 $1 \leq i \leq k$ ， $e_{i}$ ，的端点是 $v_{i - 1}$ 和 $v_{i}$ 、称 $w$ 是从 $v_{0}$ 到 $v_{k}$ 的一条途径，或一条 $(v_{0}, v_{k})$ 途径

途径中边数称为途径的长度

$v_{0}$ ， $v_{k}$ 分别称为途径的起点与终点，其余顶点称为途径的内部点

一条途径的起点与终点重合时叫做闭途径

边不重复的途径称为图的一条迹，起点与终点重合时叫做闭迹，也称为回路

顶点不重复的途径称为图的一条路，起点与终点重合时叫做圈。显然顶点不重复时边也不重复，所以迹是包含路的。

Success

起点与终点重合的途径、迹、路分别称为图的闭途径、闭迹与圈。闭迹也称为回路

长度为 $k$ 的圈称为 $k$ 圈， $k$ 为奇数时称为奇圈， $k$ 为偶数时称为偶圈

圈的充分条件¶

若 $δ \geq 2$ ，则 $G$ 中必然含有圈。

Abstract

只就连通图证明即可！

设 $W = v_{1} v_{2} \dots v_{k - 1} v_{k}$ 是 $G$ 中的一条最长路。由于 $δ \geq 2$ ，所以 $v_{k}$ 必然有相异于 $v_{k - 1}$ 的邻接顶点。

又 $W$ 是连通图 $G$ 中最长路，所以，这样的邻接点必然是 $v_{1} v_{2} \dots v_{k - 2}$ 中之一。设该点为 $v_{m}$ ，则 $v_{m} v_{m + 1} \dots v_{k} v_{m}$ 为 $G$ 中圈。

偶图的充要条件¶

一个图是二部图 (偶图) 当且当它不包含奇圈

证明必要性:

设 $G$ 是具有二分类 $(X, Y)$ 的偶图，并且 $C = v_{0} v_{1} \dots v_{k} v_{0}$ 是 $G$ 的一个圈

不失一般性，可假定 $v_{0} \in X$ ；

一般说来， $v_{2 i} \in X, v_{2 i + 1} \in Y$ ；

又因为 $v_{0} \in X$ ，所以 $v_{k} \in Y$ ，由此即得 $C$ 是偶圈

证明充分性:

在 $G$ 中任意选取点 $u$ ，定义 $V$ 的分类如下:

$X = {x | d (u, x) 是偶数, x \in V (G)}$ ；
$Y = {y | d (u, y) 是奇数, y \in V (G)}$ ；

（接下来证明 $X$ 中任意两点 $v, w$ 不邻接）

设 $v, w$ 是 $X$ 中任意两个顶点， $P$ 是一条最短 $(u, v)$ 路，而 $Q$ 是一条最短 $(u, w)$ 路，设 $u_{1}$ 是 $P$ 和 $Q$ 的最后一个交点：

$偶图充分必要条件充分性证明$

由于 $P, Q$ 是最短路，所以， $P, Q$ 中 $u$ 到 $u_{1}$ 段长度相同，因此奇偶性相同

又 $P, Q$ 的长均是偶数，所以， $P, Q$ 中 $u_{1} v$ 段和 $u_{1} w$ 段奇偶性相同

如果 $v, w$ 邻接则可得到奇圈，矛盾！

两顶点的距离¶

图中顶点 $u$ 与 $v$ 的距离: $u$ 与 $v$ 间最短路的长度称为 $u$ 与 $v$ 间距离。记为：

d (u, v)

如果 $u$ 与 $v$ 间不存在路，定义：

d (u, v) = 0

两顶点的连通性¶

图 $G$ 中点 $u$ 与 $v$ 说是连通的，如果 $u$ 与 $v$ 间存在通路。否则称 $u$ 与 $v$ 不连通。

点的连通关系是等价关系

非连通图中每一个极大连通部分，称为 $G$ 的连通分支

$G$ 的连通分支的个数，称为 $G$ 的分支数，记为：

ω (G)

图的连通性¶

如果图 $G$ 中任意两点是连通的，称 $G$ 是连通图，否则，称 $G$ 是非连通图

连通图的性质¶

在 $n$ 阶连通图中：

至少有 $n - 1$ 条边
如果边数大于 $n - 1$ ，则至少有一条闭迹
如果恰有 $n - 1$ 条边，则至少有一个奇度点

（2）证明:

若 $G$ 中没有 $1$ 度顶点，由握手定理:

2 m = \sum_{v \in V (G)} d (v) \geq 2 n \Rightarrow m \geq n \Rightarrow m > n - 1

（3）证明：

若不然， $G$ 中顶点度数至少为 $2$ ，于是由握手定理：

2 m = \sum_{v \in (G)} d (v) \geq 2 n \Rightarrow m \geq n \Rightarrow m > n - 1

这与 $G$ 中恰有 $n - 1$ 条边矛盾！

补图的连通性¶

若图 $G$ 是不连通的，则它的补图 $\overset{―}{G}$ 是连通图.

证明：设 $u, v$ 是 $G$ 的任意两个顶点:

若 $u$ 和 $v$ 在 $G$ 中不邻接，则在 $\overset{―}{G}$ 中它们邻接，从而 $\overset{―}{G}$ 是连通的
若 $u$ 和 $v$ 在 $G$ 中邻接，它们属于 $G$ 的同一分支；在另一个分支中有一点 $w$ ，在 $\overset{―}{G}$ 中 $u$ 和 $v$ 均与 w 邻接，即 $u w v$ 是一条通道，从而 $\overset{―}{G}$ 是连通的

连通图充分条件 1¶

设图 $G$ 为 $n$ 阶图，若 $G$ 中任意两个不相邻的点 $u$ 和 $v$ ，有：

d (u) + d (v) \geq n - 1

则 $G$ 是连通的，且 $d (G) \leq 2$

证明：对 $G$ 中任意两点 $x$ 和 $y$ ，一定存在一条长度至多为 $2$ 的连接 $x$ 和 $y$ 的路

当 $x y \in E (G)$ 时上述论断显然成立；

当 $x y \notin E (G)$ 时：

可以证明，存在点 $w$ ，它与 $x$ 和 $y$ 同时邻接。反证法：

若不然，在 $G$ 的剩下 $n - 2$ 个顶点中，假设：

有 $k$ 个与 $x$ 邻接，但与 $y$ 不邻接；
有 $l$ 个与 $y$ 邻接，但与 $x$ 不邻接；
有 $m$ 个顶点和 $x, y$ 均不邻接。

则： $d (x) = k$ ， $d (y) = l$

由于 $k + l + m = n - 2$

所以 $d (x) + d (y) = n - m - 2 \leq n - 2$ ，矛盾！

连通图充分条件 2¶

图 $G$ 为 $n$ 阶图，若 $δ \geq \frac{n - 1}{2}$ ，则 $G$ 连通

证明:

对 G 中任意两个不相邻顶点 u 与 v，有:

d (u) + d (v) \geq \frac{n - 1}{2} + \frac{n - 1}{2} = n - 1

所以，G 是连通的。

Warning

该定理的界是紧的 (Sharpness)。即不能再修改!

例如: 设 G 由两个分支作成的图，两个分支均为 $K_{m}$ ，则 G 中不相邻顶点度数之和恰为 n-2 . ( n=2m )

图的直径¶

连通图 G 的直径定义为

d (G) = max {d (u, v) | u, v \in V (G)}

如果 G 不连通，图 G 的直径定义为 $d (G) = \infty$

直径相关性质¶

设 G 是具有 m 条边的 n 阶单图，若 G 的直径为 2 且 $δ = n - 2$ ，则 $m \geq 2 n - 4$

证明：

设 $d (v) = Δ = n - 2$ ，设 v 的邻接点为 $v_{1}, v_{2}, \dots, v_{n - 2}$ ，u 是剩下的一个项点。

由于 $d (G) = 2$ 且 u 不能和 v 邻接，所以 u 至少和 $v_{1}, v_{2}, \dots, v_{n - 2}$ 中的一个顶点邻接。否则有 $d (G) > 2$ ; 不妨假设 u 和 $v_{1}, v_{2}, \dots, v_{k}$ 邻接。

为了保证 u 到各点距离不超过 2 , $v_{k + 1}, \dots, v_{n - 2}$ 这些頂点的每一个必须和前面 $v_{1}, v_{2}, \dots, v_{k}$ 中某点邻接，这样，图中至少又有 n-2 条边。总共至少有 2n-4 条边。