# 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

-
What about the graph with two nodes and no edges? –  Hagen von Eitzen Nov 2 '12 at 19:03
@Hagen: It doesn’t satisfy the hypothesis. –  Brian M. Scott Nov 2 '12 at 19:16

Suppose that $vw\in E$ is such that $f(v)\ne f(w)$. Since $x\ne y$, we may assume without loss of generality that $x<y$.

Now $d_G(v,w)=1\le 2$, so $x\le w$ and $y\le v$. Moreover, $d_G(w,w)=0\le 2$, so $y\le w$. Since $x<y$, it follows that $x\ne v$ and $x\ne w$. Suppose that $d_G(x,v)=1$; then the edges $xv$ and $vw$ are a path of length $2$ from $x$ to $w$, so $d_G(x,w)\le 2$, and therefore $y\le x<y$, which is absurd. Thus, $d_G(x,v)=2$, and there is a vertex $z$ distinct from $x$ and $v$ such that $xz,zv\in E$. To show that the vertices $x,z,v,w$ and the edges $xz,zv,vw$ are a $P_4$, you need only show that $w\notin\{x,z,v\}$. We already know that $w\ne x$ and $w\ne v$, so you really need only show that $w\ne z$.

HINT: If $w=z$, then $d_G(x,w)\le 2$.

-
Draw the graph for this exercise, please –  Bun pentru tine - Nov 2 '12 at 21:09
@Bunpentrutine-: It’s not really possible: there are infinitely many different graphs that satisfy the hypotheses of the theorem. At most you can sketch different configurations of the vertices $v,w,x,y,z$ and eliminate the impossible ones using the reasoning in my answer. –  Brian M. Scott Nov 2 '12 at 21:13
an example , please –  Bun pentru tine - Nov 2 '12 at 21:49
@Bunpentrutine-: Can you find a graph that satisfies the hypotheses of the theorem? If so, you can draw it and pick out $v,w,x,y$, and $z$ for yourself. Draw several and do the same with each of them, and it may help you to see what’s going on with the argument, though I don’t guarantee it. Or is the problem that you can’t find an example of a graph satisfying the hypotheses of the theorem? –  Brian M. Scott Nov 2 '12 at 21:54
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) –  Bun pentru tine - Nov 4 '12 at 14:19

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.

-
This is all the proof? –  Bun pentru tine - Nov 5 '12 at 8:09