Exercise 5.

Consider the graph \(G = (V, E)\) with \(V = \{a,b,c,d,e,f,g\}\) and \(E = \{ab, ac, af, bg, cd, ce\}\) (here we are using the shorthand for edges: \(ab\) really means \(\{a,b\}\text{,}\) for example).

  1. Is the graph \(G\) isomorphic to \(G' = (V', E')\) with \(V' = \{t, u, v, w, x, y, z\}\) and \(E' = \{tz, uv, uy, uz, vw, vx\}\text{?}\) If so, give the isomoprhism. If not, explain how you know.

  2. Find a graph \(G''\) with 7 vertices and 6 edges which is NOT isomorphic to \(G\text{,}\) or explain why this is not possible.

  3. Write down the degree sequence for \(G\text{.}\) That is, write down the degrees of all the vertices, in decreasing order.

  4. Find a connected graph \(G'''\) with the same degree sequence of \(G\) which is NOT isomorphic to \(G\text{,}\) or explain why this is not possible.

  5. What kind of graph is \(G\text{?}\) Is \(G\) complete? Bipartite? A tree? A cycle? A path? A wheel?

  6. Is \(G\) planar?

  7. What is the chromatic number of \(G\text{?}\) Explain.

  8. Does \(G\) have an Euler path or circuit? Explain.

Solution.
in-context