Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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.

Illustration of a path between $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$.

share|cite|improve this answer
Draw the graph for this exercise, please – Bun pentru tine - Nov 5 '12 at 6:58
As you wish.... – Douglas S. Stones Nov 5 '12 at 7:04
Thank you! but why the drawing is only f (u) and v? – Bun pentru tine - Nov 5 '12 at 7:30
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.