完全图

如果图 G 中的每个顶点都与其他所有顶点相连，则称图 G 为完全图。因此，完全图 G 必须是连通的。具有 n 个顶点的完全图用 K_n 表示。图显示了 K₁ 到 K₆ 的图。

正则图

如果一个图的所有顶点的度数都相同，则称该图为正则图或 K-正则图。所有顶点度数为 2 的图称为 2-正则图。完全图 K_n 是度数为 n-1 的正则图。

示例 1：画出度数为 2 和 3 的正则图。

解答：度数为 2 和 3 的正则图如图所示。

示例 2：画一个具有五个顶点的 2-正则图。

解答：具有五个顶点的 2-正则图如图所示。

示例 3：画一个具有五个顶点的 3-正则图。

解答：不可能画出一个具有五个顶点的 3-正则图。3-正则图必须有偶数个顶点。

二分图

如果图 G=(V, E) 的顶点 V 可以划分为两个子集 V₁ 和 V₂，使得 G 的每条边都连接 V₁ 中的一个顶点和 V₂ 中的一个顶点，则称 G 为二分图。它用 K_mn 表示，其中 m 和 n 分别是 V₁ 和 V₂ 中的顶点数。

示例：画出二分图 K_2,4 和 K_3,4。假设边数任意。

解答：首先在两个平行列或行上画出适当数量的顶点，然后将一个列或行中的顶点与另一个列或行中的顶点连接起来。二分图 K_2,4 和 K_3,4 分别如图所示。

完全二分图

如果图 G = (V, E) 的顶点 V 可以划分为两个子集 V₁ 和 V₂，使得 V₁ 中的每个顶点都与 V₂ 中的每个顶点相连，则称 G 为完全二分图。由于 V₁ 中的 m 个顶点中的每一个都与 V₂ 中的 n 个顶点中的每一个相连，所以完全二分图中的边数为 m*n。

示例：画出完全二分图 K_3,4 和 K_1,5。

解答：首先在两个平行列或行中画出适当数量的顶点，然后将第一个列或行中的顶点与第二个列或行中的所有顶点连接起来。图 K_3,4 和 K_1,5 如图所示。

欧拉通路

欧拉路径是通过图的路径，其边列表恰好包含图的每条边一次。

欧拉回路：欧拉回路是图中的一条路径，其中起始顶点再次作为终止顶点出现。

欧拉图：欧拉图是具有欧拉回路的图。欧拉回路使用每条边恰好一次，但顶点可能重复。

示例：图所示的图是欧拉图。确定该图的欧拉回路。

解答：该图的欧拉回路是：

              V₁,V₂,V₃,V₅,V₂,V₄,V₇,V₁₀,V₆,V₃,V₉,V₆,V₄,V₁₀,V₈,V₅,V₉,V₈,V₁

对于一个没有奇数度顶点的连通图，我们可以得到一个欧拉回路。

陈述并证明欧拉定理

陈述：考虑任何连通平面图 G= (V, E)，它有 R 个区域、V 个顶点和 E 条边。则 V+R-E=2。

证明：使用数学归纳法来证明这个定理。

归纳基础：假设每条边 e=1。然后我们有两种情况，其图如图所示。

在图中：我们有 V=2 且 R=1。因此 2+1-1=2。

在图中：我们有 V=1 且 R=2。因此 1+2-1=2。

因此，归纳基础已得到验证。

归纳步骤：我们假设该公式适用于具有 K 条边的连通平面图。

设 G 是一个具有 K+1 条边的图。

首先，我们假设 G 中没有回路。现在，取一个顶点 v 并找到一条从 v 开始的路径。由于 G 是无回路的，每当我们找到一条边时，我们就会得到一个新顶点。最后，我们将到达一个度数为 1 的顶点 v。因此，我们无法继续前进，如图所示。

现在移除顶点 v 和与之相连的边。因此，我们得到一个具有 K 条边的图 G*，如图所示。

因此，根据归纳假设，欧拉公式适用于 G*。

现在，由于 G 的边数比 G* 多一条，顶点数比 G* 多一个，区域数与 G* 相同。因此，该公式也适用于 G。

其次，我们假设 G 包含一个回路，并且 e 是回路中的一条边，如图所示。

现在，由于 e 是两个区域边界的一部分。因此，我们只删除该边，就得到了一个具有 K 条边的图 G*。

因此，根据归纳假设，欧拉公式适用于 G*。

现在，由于 G 的边数比 G* 多一条，区域数比 G* 多一个，顶点数与 G* 相同。因此，该公式也适用于 G，这验证了归纳步骤，从而证明了该定理。