How is this graph Hamiltonian and Eulerian?

In summary, the conversation discusses whether a graph is Hamilton and Eulerian. One participant believes the graph is wrong since there is no path that covers all paths only once. Another participant provides an explicit path that covers all nodes exactly once, proving that the graph is Hamiltonian but not Eulerian due to 4 knots with an odd degree. The conversation concludes that the website may have the graph labeled incorrectly.
  • #1
jaus tail
615
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?
g38.gif

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:
Physics news on Phys.org
  • #3
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 jaus tail
  • #4
fresh_42 said:
It is a Hamilton graph, but it is not an Euler graph, since there are 4 knots with an odd degree.
https://en.wikipedia.org/wiki/Eulerian_path

It is not Eulerian because there is one node with an odd degree. :oldtongue: :oldbiggrin:
 
  • Like
Likes jaus tail
  • #5
Thanks. Guess the website has it wrong then.
 

1. What is a Hamiltonian graph?

A Hamiltonian graph is a graph in which there exists a cycle that passes through each vertex exactly once. In other words, it is a graph that can be traversed without repeating any vertices.

2. How do you determine if a graph is Hamiltonian?

There is no simple algorithm to determine if a graph is Hamiltonian. However, there are some necessary conditions that a graph must satisfy in order to be Hamiltonian, such as having a minimum degree of n/2, where n is the number of vertices in the graph. Additionally, certain types of graphs, such as complete graphs and cycles, are always Hamiltonian.

3. What is an Eulerian graph?

An Eulerian graph is a graph in which there exists a cycle that includes every edge exactly once. In other words, it is a graph that can be traversed without repeating any edges.

4. How do you determine if a graph is Eulerian?

A graph is Eulerian if and only if every vertex has an even degree. This means that the number of edges connected to each vertex must be an even number. Additionally, the graph must be connected.

5. Can a graph be both Hamiltonian and Eulerian?

Yes, a graph can be both Hamiltonian and Eulerian. In fact, all Hamiltonian graphs are also Eulerian, but not all Eulerian graphs are Hamiltonian. This is because a Hamiltonian cycle necessarily includes all edges, making it also an Eulerian cycle.

Similar threads

  • Programming and Computer Science
Replies
2
Views
1K
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
502
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
90
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
Back
Top