Question

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

Short answer

The given two graphs are isomorphic.

Step-by-step solution

Determine whether or not two graphs are isomorphic.

Both graphs contain a lot of symmetry, and the degrees of the vertices are the same, thus it's reasonable to assume that they're isomorphic. Let's see if one can make the correspondence f. First, notice that the first graph has a four-cycle\({{\rm{u}}_{\rm{1}}}{\rm{,}}{{\rm{u}}_{\rm{5}}}{\rm{,}}{{\rm{u}}_{\rm{2}}}{\rm{,}}{{\rm{u}}_{\rm{6}}}{\rm{,}}{{\rm{u}}_{\rm{1}}}\). Assume that it corresponds to the four-cycle \({{\rm{v}}_{\rm{1}}}{\rm{,}}{{\rm{v}}_{\rm{2}}}{\rm{,}}{{\rm{v}}_{\rm{3}}}{\rm{,}}{{\rm{v}}_{\rm{4}}}{\rm{,}}{{\rm{v}}_{\rm{1}}}\)in the second graph. Let \({\rm{f}}\left( {{{\rm{u}}_{\rm{1}}}} \right){\rm{ = }}{{\rm{v}}_{\rm{1}}}{\rm{,f}}\left( {{{\rm{u}}_{\rm{5}}}} \right){\rm{ = }}{{\rm{v}}_{\rm{2}}}{\rm{,f}}\left( {{{\rm{u}}_{\rm{2}}}} \right){\rm{ = }}{{\rm{v}}_{\rm{3}}}{\rm{,andf}}\left( {{{\rm{u}}_{\rm{6}}}} \right){\rm{ = }}{{\rm{v}}_{\rm{4}}}\)be the variables. The rest of the assignments are forced: because \({{\rm{u}}_{\rm{7}}}\)is the other vertex adjacent to\({{\rm{u}}_1}\), \({\rm{f}}\left( {{{\rm{u}}_{\rm{7}}}} \right){\rm{ = }}{{\rm{v}}_{\rm{6}}}\)is the other vertex adjacent to\({{\rm{v}}_{\rm{1}}}\)(which is \({\rm{f}}\left( {{{\rm{u}}_1}} \right)\)and \({{\rm{v}}_{\rm{6}}}\)is the other vertex adjacent to \({{\rm{v}}_{\rm{1}}}\)(which is \({\rm{f}}\left( {{{\rm{u}}_1}} \right)\)In the same way\({\rm{f}}\left( {{{\rm{u}}_{\rm{3}}}} \right){\rm{ = }}{{\rm{v}}_{\rm{7}}}{\rm{,f}}\left( {{{\rm{u}}_{\rm{8}}}} \right){\rm{ = }}{{\rm{v}}_{\rm{8}}}{\rm{,andf}}\left( {{{\rm{u}}_{\rm{4}}}} \right){\rm{ = }}{{\rm{v}}_{\rm{5}}}\). Simply ensure that the vertices in the second graph that correspond to the vertices in the four-cycle \({{\rm{v}}_5}{\rm{,}}{{\rm{v}}_6}{\rm{,}}{{\rm{v}}_7}{\rm{,}}{{\rm{v}}_8}{\rm{,}}{{\rm{v}}_5}\)form a four-cycle in that order. Our correspondence works because these vertices form the four-cycle\({{\rm{u}}_{\rm{4}}}{\rm{,}}{{\rm{u}}_{\rm{7}}}{\rm{,}}{{\rm{u}}_{\rm{3}}}{\rm{,}}{{\rm{u}}_{\rm{8}}}{\rm{,}}{{\rm{u}}_{\rm{4}}}\).

Result.

Therefore, the given two graphs are isomorphic.