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

1

If $f(u)=f(v)$ then $u$ and $v$ are in same connected component (by definition).

Now suppose $f(u) 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.

Illustration of a path between <span class=f(u) and $v$">

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

  • 0
    The vertices $u$ and $v$ are arbitrary, provided that they belong to the same component and f(u). Once they are chosen, only the shortest path between $f(u)$ and $v$ matters, which is what I've drawn.2012-11-05