Exercise 5.

Consider the following two graphs:

\(G_1\)

\(V_1=\{a,b,c,d,e,f,g\}\)

\(E_1=\{\{a,b\},\{a,d\},\{b,c\},\{b,d\},\{b,e\},\{b,f\},\{c,g\},\{d,e\}\text{,}\)

\(\{e,f\},\{f,g\}\}\text{.}\)

\(G_2\)

\(V_2=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}\text{,}\)

\(E_2=\{\{v_1,v_4\},\{v_1,v_5\},\{v_1,v_7\},\{v_2,v_3\},\{v_2,v_6\}\text{,}\)

\(\{v_3,v_5\},\{v_3,v_7\},\{v_4,v_5\},\{v_5,v_6\},\{v_5,v_7\}\}\)

  1. Let \(f:G_1 \rightarrow G_2\) be a function that takes the vertices of Graph 1 to vertices of Graph 2. The function is given by the following table:

    \(x\) \(a\) \(b\) \(c\) \(d\) \(e\) \(f\) \(g\)
    \(f(x)\) \(v_4\) \(v_5\) \(v_1\) \(v_6\) \(v_2\) \(v_3\) \(v_7\)

    Does \(f\) define an isomorphism between Graph 1 and Graph 2?

  2. Define a new function \(g\) (with \(g \ne f\)) that defines an isomorphism between Graph 1 and Graph 2.

  3. Is the graph pictured below isomorphic to Graph 1 and Graph 2? Explain.

    A graph with seven vertices.  Six of the vertices are arranged in rectangle, three across and two down, with edges around the perimeter.  The seventh vertex is in the center, with edges connecting it to the vertices directly above and below it, and to the two outside vertices in the bottom row.
in-context