# Isomorphism Proof

• October 3rd 2008, 11:56 AM
Ultros88
Isomorphism Proof
I'm having difficulty with this proof since I'm not sure how the two iffs affect the layout of the solution:

Show that two simple graphs $G$ and $H$ are isomorphic if and only if there is a bijection $\vartheta : V(G) \rightarrow V(H)$ such that $uv \in E(G)$ if and only if $\vartheta (u) \vartheta (v) \in E(H)$.

Any help would be much appreciated,
Ultros
• October 3rd 2008, 01:55 PM
Plato
It is considered impossible to prove a definition.
If the above is not given as the definition of isomorphic graphs, then how does your textbook define isomorphic graphs?
• October 3rd 2008, 03:46 PM
Ultros88
Defn of Isomorphic
Two graphs G and H are said to be isomorphic if there are bijections $\theta : V(G) \rightarrow V(H)$ and $\phi : E(G) \rightarrow E(H)$ such that $\psi_G (e) = uv$ if and only if $\psi_H (\phi (e)) = \theta (u) \theta (v)$. Where $\psi$ is a graph's incidence function, e is an edge, and u and v are vertices.