Bondy Murty Graph Theory Exercise 1.2.3

Exercise 1.2.3

These are the solutions to the exercises of the book Graph Theory with Applications by J. A. Bondy and U. S. R. Murty.

Let us try and construct an isomorphism from one graph to the other. Let us call the graph on the left: $G$ and the graph on the right $H$ and assign the following labels:

Graph $G$

Graph $H$

Let $\theta (v_4)=a$ because the two vertices are “similar”, they have the same number of edges touching the vertices in particular two multiple edges. However $v_4$ is adjacent to $v_3$ (the only vertex with a loop in graph $G$ ), whereas $a$ is not adjacent to $c$ (the only vertex with a loop in graph $H$ ). Hence the two graphs have a different structure.

The solutions of all the exercises of “Graph Theory with Applications” by J. A. Bondy and U. S. R. Murty, are available for download as a pdf file! Click the button below.