1. Isomorphism

Prove that the following two graphs are isomorphic, i.e., write down an isomorphismbetween them.

Ok so if I find that the graphs have the same number of vertices which they do being 6 that matches, then the same number of edges being 8 that matches now the degrees on each vertice need to match its neighbour

a -3,q-3 c-2,u-2 t-3 ,d-3 f-3,r-3 s-3,e-3 b-2,v-2 therefore it is an isomorphism as all vertices ,edges and degrees match
Have I done this correctly ?
If not sorry..um should I write ad3,qd3 as a degree 3 ,q degree 3 ? for example

cheers

2. Re: Isomorphism

An isomorphism will take the form of a function:

$\varphi: V(G_1) \to V(G_2)$ defined by

$\varphi(a) = q$

$\varphi(b) = v$

$\varphi(c) = u$

$\varphi(d) = t$

$\varphi(e) = s$

$\varphi(f) = r$

To show that this is an isomorphism, you must show that it is a bijection. That is evident by its definition. Next, you must show that for every pair of vertices, $(v_1,v_2) \in G_1\times G_1$, the pair $(\varphi(v_1),\varphi(v_2))\in G_2 \times G_2$ are incident vertices if and only if $(v_1,v_2)$ are two incident vertices (meaning if and only if there exists an edge between them).

Example: the 8 edges of $G_1$ are incident to $(a,c),(c,d),(a,f),(f,d),(a,b),(b,e),(e,f),(e,d)$. Those, along with the same pairs written in reverse order, are the only edges. Every edge of $G_1$ is represented by exactly one of those pairs. This allows you to verify that the isomorphism preserves edges.

3. Re: Isomorphism

Thanks SlipetEternal, i'd like to borrow your brain for my next in class lecture quiz ...if only .
I'm off to bed now (australia)thanks for the help ..I will ponder your teachings..
Till next time
Not sure if you're in the states but heres hoping Houston gets through ok with a few blessings,
Cheers