Prove that if there are $vw ∈ E(G)$ such that $f(v) \neq f(w)$ then $G$ contains the graph $P_4$ as an induced subgraph Let $G = (V,E)$ be a graph with $V = \{1, \dots , n\}$. Consider the function $f : V \to V$ defined by $$f(v) = \min\{u\mid u \in V, d_G(v, u) \leq 2\}$$
Prove that if there are $vw \in E(G)$ such that $f(v) \neq f(w)$ then $G$ contains the graph $P_4$ as an induced subgraph

Assume $f(v)<f(w)$.  If this is not true, swap the labels for $v$ and $w$.
Claim: $G$ has an induced subgraph as depicted below:

If $\mathrm{dist}(v,f(v))<2$, or there are any other edges induced by the above subgraph, then $f(w) \leq f(v)$, giving a contradiction.
