Induced subgraphs of cycles

Question

Let $G$ be a graph of order $5$ such that the induced subgraph formed by removing any $2$ vertices in $G$ is not isomorphic to the nullgraph or $C_3.$ It seems clear that $G = C_5.$ Could someone advise me how to prove this assertion? Hints will suffice, thank you.

Answer 1

You may already know the result that for a $6$-vertex graph, this is impossible: in any $6$-vertex graph $G$, there is either a $3$-vertex empty subgraph, or a $3$-vertex $C_3$ subgraph. (Usually we say $K_3$ - the $3$-vertex clique - rather than $C_3$ - the $3$-vertex cycle, even though they're the same, because the most common generalization of this result is to larger cliques and not to larger cycles.)

If not, let me summarize the proof. You pick a vertex $v$, and consider two cases:

• There are three vertices $w_1,w_2,w_3$ all adjacent to $v$. Then having any edge $w_iw_j$ creates a $K_3$ induced by $\{v,w_i,w_j\}$, and having no such edge creates an empty subgraph induced by $\{w_1,w_2,w_3\}$.
• There are three vertices $w_1,w_2,w_3$ all not adjacent to $v$. Then missing any edge $w_iw_j$ creates an empty subgraph induced by $\{v, w_i, w_j\}$, and having all three such edges creates $K_3$ induced by $\{w_1,w_2,w_3\}$.

(One of these cases must happen by the pigeonhole principle, because out of $5$ other vertices either three are neighbors of $v$ or else three are non-neighbors of $v$.)

Now for a hint as to how to proceed in your case: consider this proof carefully, and think about cases where it would also work for a $5$-vertex graph. We know it doesn't work for all $5$-vertex graphs, because it doesn't work for $C_5$. But we can try to show that the proof still works unless the graph has some specific property, and then try to show that this property implies that the graph is $C_5$.

(This is a really common technique throughout math in general.)