When can we speak of an Eulerian graph?

Question

I see A LOT of different definitons for this one, yet I want to know what exactly is an Eulerian graph.

I know for sure that a graph is Eulerian if every vertex has an even degree.

Now, is it also true that a graph is Eulerian when there are 2 vertices with odd degree (and the rest should be even)?

So, I am solving these now, and from the above given "definitions", I came up with:

1) First one can't be Eulerian as it has more than two vertices who are odd

2) Second one can't be Eulerian as it has more than two vertices who are odd

3) Third one can't be Eulerian as it has more than two vertices who are odd

4) Must be Eulerian as every graph has an even degree.

Is this correct?

Answer 1

Generally, an Eulerian graph is defined in one of two ways:

• A graph in which all vertex degrees are even, or
• A connected graph in which all vertex degrees are even.

Also, a (sometimes, connected) graph in which all but two vertex degrees are even is called semi-Eulerian. This according to Wikipedia.

If I were you, I wouldn't worry about the terminology, since different people use it slightly differently, and usually they will define their terms before using them. I would be sure to understand the theorems:

Theorem 1. A graph $G$ contains an Eulerian circuit - a circuit which uses every edge exactly once - if and only if it is connected (except possibly for isolated vertices) and the degree of every vertex is even.

Theorem 2. A graph $G$ contains an Eulerian trail - a trail which uses every edge exactly once - if and only if it is connected (except possibly for isolated vertices) and there are $0$ or $2$ vertices with odd degree.

There are analogous theorems for directed graphs, and a directed graph that satisfies their hypotheses is sometimes also called Eulerian or semi-Eulerian, respectively.

I use the word "trail" and "circuit" here due to yet another ambiguity in terminology. I prefer the following set of definitions:

• A trail in $G$ is a sequence $(v_1, v_2, \dots, v_k)$ of vertices of $G$, possibly with repetition, with the only constrain that for $1 \le i < k$, $v_i v_{i_1}$ is an edge of $G$.
• A circuit in $G$ is a trail $(v_1, v_2, \dots, v_k)$ in which $v_1 = v_k$: it returns to the start.
• A path in $G$ is a trail in which all vertices are distinct.
• A cycle in $G$ is a circuit in which, except for $v_1 = v_k$, all vertices are distinct.

But often, these are called "path", "cycle", "simple path", and "simple cycle", respectively. Alternate terms include "walk" for "trail" and "closed walk" or "tour" for "circuit". Also, path graphs and cycle graphs are often referred to as "paths" and "cycles" colloquially. There's a lot of terminology!