Why does a graph claim to be both Hamiltonian and Eulerian?

4 replies · 2K views · last reply
jaus tail
Messages
613
Reaction score
48
Homework Statement
Is the graph Hamilton and Eulerian?
Relevant Equations
Hamilton: Path exists that covers all nodes. Starting and Ending node is same. Each node covered only once.
Eulerian: Path exists that covers all paths. Starting and ending node is same. Each path covered only once.
Is the graph Hamilton and Eulerian?
Graph with eight vertices drawn as magenta circles and blue edges, arranged in a left-to-right symmetric layout with a single vertex at each end.

The website says the graph is Hamilton and Eulerian but I think it's wrong.
Ref: https://scanftree.com/Graph-Theory/Eulerian-and-Hamiltonian-Graphs
There is no path that covers all paths only once. Any help? I think the graph is drawn wrongly.
 
Last edited by a moderator:
An explicit path that covers all nodes exactly once is for example the following:

Start entirely left, move one right up, one right down, one right up and one rigjt up. Then, you are entirely right. Then move one down, one left, and one left up.

Thus your path is Hamiltonian.

The graph is not Eulerian, and the easiest way to see this is to use the theorem that @fresh_42 used.
 
  • Like
Likes   Reactions: jaus tail