一个流行的游戏是用钢笔画画如下三幅图，每条线恰好画一次。在画图的时候钢笔不要从纸上离开。作为一个附加的问题，要在结束画图时，使钢笔回到开始画图时的起点上。

第一个图仅当起点在左下角或右下角时可以画出，而且不可能结束在起点处。

第二个图容易画出，它的终止点和起点相同。

第三个图在游戏的限制条件下根本画不出来。

我们可以通过给每个交点指定一个顶点而把这个问题转化成图论问题。如下图：

将问题转化之后，我们必须在图中找出一条路径，使得该路径对图的每条边恰好访问一次。如果我们要解决“附加的问题”，那么我们就必须找到一个圈，该圈恰好经过每条边一次。这种图论问题在1736年由欧拉解决，它标志着图论的诞生。根据特定问题的叙述不同，这种问题通常叫做欧拉路经（Euler path，有时称欧拉环游-----Euler tour）或欧拉回路（Euler circuit)问题。虽然欧拉环游和欧拉回路问题少有不同，但是却有相同的基本解。

能够做的第一个观察是，其终点必须在起点上的欧拉回路只用当图是连通的，并且每个顶点的度（即，边的条数）是偶数时才有可能存在。这是因为，在欧拉回路中，一个顶点有边进入，则必然有边离开。如果任一顶点的度为奇数，那么实际上我们早晚将会达到这样一种地步，即只有一条进入v的边上位访问到，若沿该边进入v点，那么我们只能停在顶点v，不可能再出来。如果恰好有两个顶点的度为奇数，那么当我们从一个奇数度的顶点出发最后终止在另一个奇数度的顶点时，仍然可能得到一个欧拉环游。这里需要注意的是，欧拉环游指的是必须访问图的每一条边但最后不一定必须回到起点的路径。如果奇数度的顶点多余两个那么欧拉环游也是不可能存在的。

所有顶点的度均为偶数的任何连通图必然有欧拉回路。

假设我们知道存在一条欧拉回路。此时，基本算法就是执行一次深度优先搜索。

主要问题在于，我们可能只访问了图的一部分而提前返回到起点。如果从起点出发的所有边均已用完，那么图中就会有的部分遍历不到。最容易补救的方法是找出尚未访问过的边的路径上的第一个顶点，并执行另外一次深度优先搜索。这将给出另外一个回路，把它拼接到原来的回路上。继续该过程直到所有的边都被遍历到为止。

上图中，容易看出有一个欧拉回路。

设从顶点5开始，我们遍历5，4，10，5。此时，我们已经无路可走。而图的大部分都还未遍历到。

此时，我们从顶点4继续进行，它仍然还有没有用到的边。结果，又得到路径4，1，3，7，4，11，10，7，9，3，4。

如果我们把这条路拼接到前面的路上，那么我就得到一条新的路径：

5，4，1，3，7，4，11，10，7，9，3，4，10，5。

此后，在剩下的图中，所有的顶点的度必然是偶数。路径上存在未被访问的边的下一个顶点是3。此时可能的回路可以是3，2，8，9，6，3。

继续拼接之后我们得到：

5，4，1，3，2，8，9，6，3，7，4，11，10，7，9，3，4，10，5。

剩下的图中，在该路径上，带有未被遍历边的下一个顶点是9,算法找到回路9，12，10，9。拼接之后得到：

5，4，1，3，2，8，9，12，10，9，6，3，7，4，11，10，7，9，3，4，10，5。

当所有的边都被遍历后，算法终止，我们得到了一个欧拉回路。

为使算法更有效，必须使用适当的数据结构。为使拼接简单，我们应把路径作为一个链表保留。为避免重复扫描邻接表，对于每一个邻接表我们必须保留一个指向最后扫描到的边的指针。当拼接进一个新的路径时，必须从拼接点开始搜索新顶点，从这个新顶点进行下一轮深度优先算法。