1
$\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, 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

  • 0
    What about the graph with two nodes and no edges?2012-11-02
  • 0
    @Hagen: It doesn’t satisfy the hypothesis.2012-11-02

2 Answers 2