# Does this $G$ graph have an Euler path?

$G$ is a simple graph whose vertex set is $\{ 1, \ldots ,100\}$, vertices $i$ and $j$ are connected if $1 \le |i-j| \le 2$.

Does an Euler path exist in $G$?

I know that

Euler’s Theorem 1 If a graph has any vertices of odd degree, then it cannot have an Euler circut. and If a graph is connected and every vertex has even degree, then it has at least one Euler circuit (usually more).

If a graph has more than $2$ vertices of odd degree, then it cannot have an Euler path.

If a graph is connected and has exactly $2$ vertices of odd degree, then it has at least one Euler path(usually more). Any such path must start at one of the odd-degree vertices and end at the other.

The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges). In every graph, the number of vertices of odd degree must be even.

## 2 Answers

HINT: You just need to calculate the degrees of all of the vertices.

• What is the degree of $1$ and $100$?
• What is the degree of $2$ and $99$?
• What is the degree of each vertex $n$ with $3\le n\le 98$?
• How many vertices of odd degree does $G$ have?

The vertex 2 has edges to 1, 3, and 4 (and hence has odd degree).

Therefore there is no Eulerian circuit.

• The question is about an Eulerian path not circuit. – bof Apr 13 '16 at 22:47
• @bof Ah, yes. My mistake. My answer is still a hint for the actual question, so I'll leave it up anyway. – Snow Apr 13 '16 at 23:30