Isomorphism Proof

Printable View

• Oct 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 $\displaystyle G$ and $\displaystyle H$ are isomorphic if and only if there is a bijection $\displaystyle \vartheta : V(G) \rightarrow V(H)$ such that $\displaystyle uv \in E(G)$ if and only if $\displaystyle \vartheta (u) \vartheta (v) \in E(H)$.

Any help would be much appreciated,
Ultros
• Oct 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?
• Oct 3rd 2008, 03:46 PM
Ultros88
Defn of Isomorphic
Two graphs G and H are said to be isomorphic if there are bijections $\displaystyle \theta : V(G) \rightarrow V(H)$ and $\displaystyle \phi : E(G) \rightarrow E(H)$ such that $\displaystyle \psi_G (e) = uv$ if and only if $\displaystyle \psi_H (\phi (e)) = \theta (u) \theta (v)$. Where $\displaystyle \psi$ is a graph's incidence function, e is an edge, and u and v are vertices.