0
$\begingroup$

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)$

1 Answers 1