Thread: another discrete math problems

Q.1
a) Determine whether the following graph has an Euler circuit. If it exists then write the circuit, if not then write the reason.
b) Determine whether the following graph has a Hamiltonian circuit. If it exists then write the circuit, if not then write the reason.

Q.2
Determine whether the graph G and G’ given below are isomorphic. If they are isomorphic then prove it, and if they are not isomorphic then give the reason.

Definitions in graph theory do differ from text to text. Usually an Eulerian Circuit is a closed path in the graph that includes each edge exactly once.
Theorem: A simple graph has an Eulerian Circuit if and only if each vertex is even.

On the other hand, a simple graph is said to be Eulerian if there is path in the graph that includes each edge exactly once.
Theorem: A simple graph is Eulerian Circuit if and only if there are at most two odd vertices.

Eulerian graphs are edge driven whereas Hamiltonian Graphs are vertex driven. Does your given graph have a cycle that includes each vertex once.


Two graphs are isomorphic if and only if there adjacency matrices are similar.