Solution 4.7.5.1.

  1. Yes, the graphs are isomorphic, which you can see by drawing them. One isomorphism is:

    \begin{equation*} f = \begin{pmatrix} a \amp b \amp c \amp d \amp e \amp f \amp g \\ u \amp z \amp v \amp x \amp w \amp y \amp t \end{pmatrix}\text{.} \end{equation*}
  2. This is easy to do if you draw the picture. Here is such a graph:

    A tree with a bottom vertex adjacent to each of three vertices in a row above it.  Each of these is adjacent to another vertex directly above them.

    Any labeling of this graph will be not isomorphic to \(G\text{.}\) For example, we could take \(V'' = \{a,b,c,d,e,f,g\}\) and \(E'' = \{ab, ac, ad, be, cf, dg\} \text{.}\)

  3. The degree sequence for \(G\) is \((3, 3, 2, 1, 1, 1, 1)\text{.}\)

  4. In general this should be possible: the degree sequence does not determine the graph's isomorphism class. However, in this case, I was almost certain this was not possible. That is, until I stumbled up this:

    A tree with a center bottom vertex adjacent to two vertices above it.  Each of these are adjacent to two vertices above them.
  5. \(G\) is a tree (there are no cycles) and as such also bipartite.

  6. Yes, all trees are planar. You can draw them in the plane without edges crossing.

  7. The chromatic number of \(G\) is 2. It shouldn't be hard to give a 2-coloring (for example, color \(a, d, e, g\) red and \(b, c, f\) blue), but we know that all bipartite graphs have chromatic number 2.

  8. It is clear from the drawing that there is no Euler path, let alone an Euler circuit. Also, since there are more than 2 vertices of odd degree, we know for sure there is no Euler path.

in-context