Use the following graph for 3 and 4. An Euler path is a path that uses every edg

Question

Use the following graph for 3 and 4. An Euler path is a path that uses every edge of a graph exactly once, that starts at one node and ends at a different node. An Euler cycle, is an Euler path that starts and ends at the same node. Does the following graph have an Euler path? Does it have an Euler cycle? If it does, then list the edges in the order they are crossed, and if it does not then explain why. A Hamiltonian path is a path that uses every node of a graph exactly once. A Hamiltonian cycle is a Hamiltonian path that starts and ends at the same node (the only node that can be visited twice). Does the graph from the preceding question have a Hamiltonian path? Does it have a Hamiltonian cycle? If it does, then show it on the graph and if it does not then explain why.

Explanation / Answer

3.

No , this graph does not has an Euler path .

All vertices have even degree . The necessary and sufficient condition for Euler path is that all vertices except first and last vertex which should be odd.

Yes, this graph has an Euler circuit 1 --- 2 ---- 3 --- 8 --- 7 --- 6 --- 5 --- 4. as all the vertices have even degree

4.

This is a Hamiltonian path or circuit as it satisfy the necessary and sufficient condition that a graph with n vertices(n>=3) is Hamiltonian if every vertex has degree n/2 (8/4= 2) or greater .

vertex degree 1 2 2 4 3 4 4 4 5 4 6 4 7 4 8 2

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.