1.行遍所有的边：欧拉图（E图）
2.行遍所有的顶点：哈密尔顿图(H图)

欧拉图

Theorem
设G是一个无向或有向图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通图（回路），为欧拉通路(回路)，具有欧拉回路的图称为欧拉图。
Corollary
1.无向图G=<V, E>具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。
2.无向图G=<V, E>具有一条欧拉回路，当且仅当G是连通的，**且所有结点的度数均为偶数。
（注：通路回不到起点，回路可以回到起点）
Theorem
有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，一个结点的入度比出度大1（终点），另一个结点的出度比入度大1（起点）。
Corollary
1.有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。

Algorithm
求无向图的欧拉回路——Fleury算法
依次选边，每选一条边就从图中删去，选取条件是：与上一条已选取的边关联，除非无别的边可选，否则不能选割边(桥)

哈密尔顿图

Theorem
设G是一个无向或有向图，若存在一条通路(回路)，经过图中每结点一次且仅一次，则称此通图（回路），为哈密尔顿通路(回路)，具有哈密尔顿回路的图称为哈密尔顿图。
Theorem
哈密尔顿图的必要条件
1.设无向图G=<V,E>是哈密尔顿图，V1是V的任意非空子集，则 ρ ( G − V 1 ) ≤ ∣ V 1 ∣ \rho(G-V1)\leq|V1| ρ(G−V1)≤∣V1∣，其中 ρ ( G − V 1 ) \rho(G-V1) ρ(G−V1)是从G中删除V1后所得到图的连通分支数。
Corollary
设无向图G=<G,E>中存在哈密尔顿通路，则对V的任意非空子集V1,都有 ρ ( G − V 1 ) ≤ ∣ V 1 ∣ + 1 \rho(G-V1)\leq|V1|+1 ρ(G−V1)≤∣V1∣+1
用必要条件判定一个图不是哈密尔顿图
1.若存在V的某个非空子集V1使得 ρ ( G − V 1 ) ≥ ∣ V 1 ∣ \rho(G-V1)\geq|V1| ρ(G−V1)≥∣V1∣，则G不是哈密尔顿图
2.有割点的图一定不是哈密尔顿图
Theorem
哈密尔顿图的充分条件
1.设G=<V,E>是具有n个结点的简单无向图，如果对任意两个不相邻的结点 u , v ∈ V u,v\in V u,v∈V，均有deg(u)+deg(v) ≥ n − 1 \geq n-1 ≥n−1，则G中存在哈密尔顿通路。
2.若是哈密尔顿回路，则deg(u)+deg(v) ≥ n \geq n ≥n
Corollary
设G=<V,E>是具有n个结点的简单无向图。当n ≥ \geq ≥ 3时，如果对任意 v ∈ V v\in V v∈V，均有deg(v) ≥ n 2 \geq \frac{n}{2} ≥2n​,则G是哈密尔顿图。

二分图

1.X ∪ \cup ∪Y=V,X ∩ Y = ∅ \cap Y=\varnothing ∩Y=∅,每条边两端点都在不同集合，用G=<X,E,Y>表示二分图。
2.如果X,Y任意两个顶点之间都有边，则称为完全二分图。记为 K i j , i = ∣ X ∣ , j = ∣ Y ∣ K_{ij},i=|X|,j=|Y| Kij​,i=∣X∣,j=∣Y∣。
3.二分图的充要条件：G至少有两个顶点，而且G中所有回路的长度都是偶数。
我们常用逆否命题来判断一个图不是偶图：无向图G不是偶图的充分必要条件是G中存在长度为奇数的回路。
二分图匹配
4.将E的子集M称作一个匹配，如果M中的任意两条边都没有公共端点。
5.边数最多的匹配称作最大匹配。
6.如果X中的所有的顶点都出现在匹配M中，则称M是X-完全匹配。
7.如果M既是X-完全匹配，又是Y-完全匹配，称M是完全匹配。
Theorem
霍尔定理
偶图G=<V1,E,V2>中存在从V1到V2的匹配的充要条件是V1中任意k个结点至少与V2中的k个结点相邻，k=1,2,3, … \dots …,|v1|,这个条件通常称为相异性条件。
Corollary
t条件（充分条件）
设G=<V1,E,V2>是一个偶图，如果满足：
1.V1中每个结点至少关联t条边；（V1中结点的最小度数）
2.V2中每个结点至多关联t条边；（V2中结点的最大度数）
则G中存在从V1到V2的匹配，其中t为正整数，这个条件通常称为t条件。

平面图

如果能够把一个无向图G的所有结点和边画在平面上，使得任何两边都不会再非结点出交叉，则称G为平面图，否则称G为非平面图。