0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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?
$\endgroup$
2
$\begingroup$

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

Therefore there is no Eulerian circuit.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.