Hamiltonian and Euler Graphs

In hamiltonian, every vertex should be visited atleast once while in euler, every edge should be touched once.

Hamiltonian paths are NP complete while Euler paths are not.

Eulerian Trail: Is a trail that visits every edge of the graph only once. It can start from any vertex and end at any vertex.
Eulerian Circuit: Same as eulerian trail but should start and stop at the same vertex.
Eulerian Graph: A graph is called Eulerian graph when it contains Eulerian circuit.
Theorem: An Eulerian trail exists in a connected graph, if and only if there are either no odd vertex or two odd vertex. If no odd vertex, then it can start and end at the same vertex but if there are 2 odd vertex then the path must begin at one odd vertex and end at other odd vertex.
Example:

Hamiltonian Trail: It is a trail of graph that visits every vertex only once and it can start from any vertex and end at any vertex.
Hamiltonian Circuit: Same as trail but should start and stop at the same vertex.
Hamiltonian Graph: A graph is called Hamiltonian graph when it contains Hamiltonian circuit.
Example:

Source:
https://www.youtube.com/watch?v=1iGGgnmoOtQ

Minimum Spanning Tree:

• A spanning tree of a graph is a tree that has all the vertices of the graph connected by some edges.
• A graph can have one or more number of spanning trees.
• If the graph has N vertices then the spanning tree will have N-1 edges.
• A minimum spanning tree (MST) is a spanning tree that has the minimum weight than all other spanning tree of the graph.

PRIMS ALGORITHM:

• It is an algorithm used to find MST for connected weighted undirected graph