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
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
-
0@Hagen: It doesn’t satisfy the hypothesis. – 2012-11-02
2 Answers
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
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
HINT: If $w=z$, then $d_G(x,w)\le 2$.
-
0Prove 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) – 2012-11-04
Assume $f(v)
Claim: $G$ has an induced subgraph as depicted below:
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.
-
0This is all the proof? – 2012-11-05