Which are isomorphic to induced subgraphs of G

graph theory

Question: Determine which of $H_1$, $H_2$ and $H_3$ are subgraphs of
the following graph G. Which are induced subgraphs of G? Which are
isomorphic to subgraphs of G? Which are isomorphic to induced subgraphs
of G?
enter image description here

Answer:
I understand that none of $H_1$, $H_2$, $H_3$ are induced subgraphs, but in regards to which are isomorphic to induced subgraphs of G… I understand that $H_1$ isn't as there's no edge between vertex b and f, $H_3$ is isomorphic to the induced subgraph of G, as all edges are included… but $H_2$ confuses me, as the paths are there (i.e. b can go to through vertex e to get to c), but for it to be induced subgraph, doesn't $b$ have to be directly adjacent to c? The answer says that it is isomoprhic to the induced subgraph of G… but I don't understand how.

Thanks

Best Answer

When you're dealing with isomorphisms of induced subgraphs, you want to temporarily forget the letters on the $H$ graphs and just ask yourself if there are induced subgraphs of $G$ that have that "shape".

  • You're right that $G$ induced by $\{A,B,C,E\}$ is isomorphic to $H_3$.
  • You're also right that there is no induced subgraph of $G$ that is isomorphic to $H_1$, but your argument is incomplete. You need to show that any subgraph of $G$ induced by the vertices of a 4-cycle would have an extra edge or edges. That's not too hard: you can argue that the vertices of a 4-cycle in $G$ are either $\{B,C,E,F\}$ or exactly one of the vertices is either $A$ or $D$, and in each of those cases you can identify an edge in the induced subgraph that is not a part of the 4-cycle.
  • In the same way, for $H_2$, you need to decide whether there is a 4-path in $G$ where the induced subgraph just has those three edges. (Hint: yes.)

As an aside, that font where $c$ looks so much like $e$ needs to die in a fire.

Related Question