Characteristics of Traversable Graph

From ProofWiki
Jump to: navigation, search

Theorem

A finite loop-multigraph is traversable if and only if it is connected and no more than two vertices are odd.


Any Eulerian trail 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$.

Note that if there is already an edge $uv$ in $G$, that will mean there is now more than one edge $uv$ in $G'$.

Thus $G'$ will then be a multigraph or loop-multigraph, and $uv$ a multiple edge.


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 trail $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