Eulerian Graph
- Tags
- math
A route starting and finishing at different vertices \( X \) and \( Y \) and passing over each edge once is only possible if \( X \) and \( Y \) have an odd Degree and all the other vertices have an even degree. A graph with this property is known as semi-eulerian. If \( X = Y \) and the route must end where it began, then all vertices must have an even degree. Such a graph is known as Eulerian.
To prove a graph is eulerian all we need to do is find a route which covers all the edges once and finishes at the start. For a graph with an odd number of nodes we'd need to back-track through them at least once to make the edge-count even (in this case you should choose the edges that add on the smallest weight) or in the case of a semi-eulerian graph we can find a route which starts at one odd nodes and ends at another odd node.
\begin{figure}
\centering
\begin{tikzpicture}
\node (A) [draw, circle] {A};
\node (B) [draw, circle, below=of A] {B};
\node (F) [draw, circle, below=of A, left=of B] {F};
\node (C) [draw, circle, below=of B] {C};
\node (E) [draw, circle, below=of F, left=of C] {E};
\node (D) [draw, circle, below=of C] {D};
\draw (A) -- (B)
(A) -- (F)
(B) -- (F)
(B) -- (E)
(B) -- (C)
(F) -- (E)
(C) -- (E)
(C) -- (D)
(E) -- (D);
\end{tikzpicture}
\caption{An example of a Semi-Eulerian graph. Nodes \( C \) and \( F \) have an odd
valency, but the rest have an even valency.}
\end{figure}\begin{figure}
\centering
\begin{tikzpicture}
\node (A) [draw, circle] {A};
\node (B) [draw, circle, below=of A] {B};
\node (F) [draw, circle, below=of A, left=of B] {F};
\node (C) [draw, circle, below=of B] {C};
\node (E) [draw, circle, below=of F, left=of C] {E};
\node (D) [draw, circle, below=of C] {D};
\draw (A) -- (B)
(A) -- (F)
(B) -- (F)
(B) -- (E)
(B) -- (C)
(F) -- (C)
(F) -- (E)
(C) -- (E)
(C) -- (D)
(E) -- (D);
\end{tikzpicture}
\caption{An example of a Eulerian graph. All nodes have an even valency and none
have an odd valency.}
\end{figure}