Bondy Murty Graph Theory Exercise 1.2.6

Exercise 1.2.5

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

( $\Rightarrow$ ) Let $G$ and $H$ be two simple graphs that are isomorphic. Therefore by definition there exists a bijection $\theta : V(G)\rightarrow V(H)$ and $\phi : E(G)\rightarrow E(H)$ such that $\psi_G(e)=uv\iff\psi_H(\phi(e))=\theta(u)\theta(v)$ . Hence there exists a bijection $\theta : V(G)\rightarrow V(H)$ such that $uv\in E(G)\iff \theta(u)\theta(v)\in E(H)$ . $\square$

( $\Leftarrow$ ) Assume that there is a bijection $\theta : V(G)\rightarrow V(H)$ such that $uv\in E(G)\iff \theta(u)\theta(v)\in E(H)$ .

Let $\phi : E(G) \rightarrow E(H)$ such that $\phi (uv)=\theta(u)\theta(v)$ . Note that since $G$ is simple, $\phi$ is well-defined. Also since $H$ is simple, then $\phi$ is one-to-one. Moreover since $uv\in E(G)\iff \theta(u)\theta(v)\in E(H)$ , there is one-to-one correspondence between the edge set of $G$ and the edge set of $H$ . Hence $\psi_G(e)=uv\iff\psi_H(\phi(e))=\theta(u)\theta(v)$ .

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.