# Prove that if $G$ is P4-free then any two vertices $u$ and $v$ are in the same connected component if and only if $f(u) = f(v)$

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,dG(v,u)≤2\}$

Prove that if $G$ is P4-free then any two vertices $u$ and $v$ are in the same connected component if and only if $f(u) = f(v)$

-

If $f(u)=f(v)$ then $u$ and $v$ are in same connected component (by definition).
Now suppose $f(u)<f(v)$ and $u$ and $v$ are in same connected component. We know $\mathrm{dist}(v,f(u)) \geq 3$ (otherwise $f(v) \leq f(u)$). So the shortest path from $v$ to $f(u)$ has at least $3$ edges.
If any four consecutive vertices on this path did not induce a $P_4$ subgraph in $G$, then we have found a shorter path from $v$ to $f(u)$. Hence $G$ contains an induced $P_4$.
The vertices $u$ and $v$ are arbitrary, provided that they belong to the same component and $f(u)<f(v)$. Once they are chosen, only the shortest path between $f(u)$ and $v$ matters, which is what I've drawn. – Douglas S. Stones Nov 5 '12 at 7:34