Condition for Graph to be Traversable

Theorem

A finite graph is traversable iff it is connected and no more than two vertices are odd.

Any Eulerian path which is not an Eulerian circuit must start and end at an odd vertex.

Proof

Let $G$ be a graph.

Suppose all the vertices are even, that is, there are no odd vertices.

Then $G$ is Eulerian, and the result holds.

Similarly, by the same result, if $G$ is Eulerian, it is by definition traversable.

So the question of graphs all of whose vertices are even is settled.

Sufficient Condition

Suppose $G$ is a connected graph for which exactly two vertices $u, v$ are odd.

Let $G'$ be the graph formed by adding the edge $uv$..

Then $G'$ will have all its vertices even, and thus by the above result be Eulerian and by definition traversable.

Such an Eulerian circuit that traverses $G'$ can be written, for example, $P' = \left({v, w, x, \ldots, t, u, v}\right)$.

Let us then remove the final edge $uv$ from $P'$ to get the path $P = \left({v, w, x, \ldots, t, u}\right)$.

It follows that the path $P = \left({v, w, x, \ldots, t, u}\right)$ is a path in $G$ which includes all edges in $G$.

Hence $P$ traverses $G$ and so $G$ is traversable.

We note that $u$ and $v$ are the odd vertices of $G$.

Necessary Condition

Suppose a graph $G$ is traversable.

Then it has a Eulerian path $P$.

If $P$ is a circuit, then $G$ is Eulerian and therefore has all even vertices.

Now, suppose $P = \left({v, w, x, \ldots, t, u}\right)$ is not a circuit.

Let $G'$ be the graph formed by adding the edge $uv$.

Then the path $P' = \left({v, w, x, \ldots, t, u, v}\right)$ is an Eulerian circuit and so $G$ is Eulerian.

Hence all the vertices of $G'$ are even.

So the degrees of vertices $u$ and $v$ in $G$ (and no other) are odd.

Again, we note that $u$ and $v$ are the odd vertices of $G$.

Hence the result.

$\blacksquare$

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 3.1$: Theorem $3.3$