Question

In Exercises \({\rm{3 - 5}}\)determine whether two given graphs are isomorphic.

Short answer

The given two graphs are not isomorphic.

Step-by-step solution

Definitions.

The number of edges that link to a vertex is the vertex's degree.

\({{\rm{G}}_1} = \left( {{V_1},{E_1}} \right)\)are two basic graphs.

\({{\rm{G}}_2} = \left( {{V_2},{E_2}} \right)\)are isomorphic if and only if there is a one-to-one and onto function \({\rm{f:}}{{\rm{V}}_{\rm{1}}} \to {{\rm{V}}_{\rm{2}}}\)that makes \({\rm{a}}\)and \({\rm{b}}\)adjacent in \({{\rm{G}}_{\rm{1}}}\)if and only if \({\rm{f}}\left( {\rm{a}} \right)\)and \({\rm{f}}\left( {\rm{b}} \right)\)are adjacent in\({{\rm{G}}_{\rm{2}}}\).

Determine whether or not two graphs are isomorphic.

It's worth noting that both graphs have eight vertices.

Let's start by calculating the degree of each vertex in the top graph.

\(\begin{array}{l}{\rm{deg}}\left( {{{\rm{u}}_{\rm{1}}}} \right){\rm{ = 4}}\\{\rm{deg}}\left( {{{\rm{u}}_{\rm{2}}}} \right){\rm{ = 4}}\\{\rm{deg}}\left( {{{\rm{u}}_{\rm{3}}}} \right){\rm{ = 4}}\\{\rm{deg}}\left( {{{\rm{u}}_{\rm{4}}}} \right){\rm{ = 4}}\\{\rm{deg}}\left( {{{\rm{u}}_{\rm{5}}}} \right){\rm{ = 4}}\\{\rm{deg}}\left( {{{\rm{u}}_{\rm{6}}}} \right){\rm{ = 4}}\\{\rm{deg}}\left( {{{\rm{u}}_{\rm{7}}}} \right){\rm{ = 4}}\\{\rm{deg}}\left( {{{\rm{u}}_{\rm{8}}}} \right){\rm{ = 4}}\end{array}\)

The degree of all vertices in the bottom graph should now be determined.

\(\begin{array}{l}{\rm{deg}}\left( {{{\rm{v}}_{\rm{1}}}} \right){\rm{ = 5}}\\{\rm{deg}}\left( {{{\rm{v}}_{\rm{2}}}} \right){\rm{ = 5}}\\{\rm{deg}}\left( {{{\rm{v}}_{\rm{3}}}} \right){\rm{ = 5}}\\{\rm{deg}}\left( {{{\rm{v}}_{\rm{4}}}} \right){\rm{ = 5}}\\{\rm{deg}}\left( {{{\rm{v}}_{\rm{5}}}} \right){\rm{ = 5}}\\{\rm{deg}}\left( {{{\rm{v}}_{\rm{6}}}} \right){\rm{ = 5}}\\{\rm{deg}}\left( {{{\rm{v}}_{\rm{7}}}} \right){\rm{ = 5}}\\{\rm{deg}}\left( {{{\rm{v}}_{\rm{8}}}} \right){\rm{ = 5}}\end{array}\)

The two graphs cannot be isomorphic since the top graph includes only vertices of degree \({\rm{4}}\)and the bottom network contains only vertices of degree\({\rm{5}}\).

Therefore, the given two graphs are not isomorphic.