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, 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

share|cite|improve this question
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$.

share|cite|improve this answer
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:

Induced $P_4$

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.

share|cite|improve this answer
This is all the proof? – Bun pentru tine - Nov 5 '12 at 8:09

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.