I'm stuck with exercise 5 page 72 of Harris, Hirst and Mossinghoff's Combinatorics and Graph Theory:
- Show that if being $H$-free implies Hamiltonicity in $2$-connected graphs (where $H$ is connected), then $H$ is $P_3$.
A $P_3$-free $2$-connected graph is indeed Hamiltonian because $P_3$-free graphs are disjoint unions of cliques, thus a $P_3$-free connected graph is complete, hence Hamiltonian.
What I'm unable to show, however, is that $P_3$ is the unique graph with such a property concerning $2$-connected graphs.
Attempt
I tried to solve the problem using contraposition.
Let $H$ be a connected graph that is not isomorphic to $P_3$ and let $n$ be its order.
Let's show that we can find a $2$-connected graph of order $\ge 3$ that are not Hamiltonian yet are $H$-free.
If $n=1$ then $H$ is $K_1$. No graph is $K_1$-free, so we're done with this case.
If $n=2$, since $H$ is connected, $H$ must be $K_2$. No connected graph of order $\ge 2$ is $K_2$-free, so we're done with this case.
If $n=$3, since $H$ is connected and $H\not\cong P_3$, $H$ must be $K_3$. Consider the following graph $G$:
By inspection, the graph is $K_3$-free. The graph is also $2$-connected as it has no cut vertex. Yet the graph is not Hamiltonian. Indeed, let $S={0,2}$ (subset of vertices of $G$). $G-S$ has $3$ connected components, yet $|S|=2<3$, hence the graph is not Hamiltonian according to exercise 10. (a) page 67:
- Let $G$ be a graph and let $S$ be a nonempty subset of $V(G)$.
(a) Prove that if $G$ is Hamiltonian, then $G-S$ has at most $|S|$ connected components
Hence the problem is solved for $H$ of order $\le 3$. But I don't see how I can keep going on to prove the result for all the other connected graphs $H$ of order $\ge 4$. Could you please help me?
Edit: As bof showed in the comments, the conclusion of the exercise should be "$H$ is a subgraph of $P_3$".
Let $G_1=K_{2,3}.$
Let $G_2$ be the graph with $9$ vertices and $12$ edges which you get by taking the graph $Y_3,$ the skeleton of a triangular prism, and subdividing each edge that is not in a triangle.
The graphs $G_1$ and $G_2$ are $2$-connected and non-Hamiltonian. Therefore, if $H$ is any graph with the property that every $2$-connected graph with no induced subgraph isomorphic to $H$ is Hamiltonian, then $H$ must be isomorphic to an induced subgraph of $G_1$ and of $G_2.$ The only connected graphs occurring as induced subgraphs of both $G_1$ and $G_2$ are $P_1,$ $P_2,$ and $P_3.$