0
$\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,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)$

1 Answers 1

1

If $f(u)=f(v)$ then $u$ and $v$ are in same connected component (by definition).

Now suppose $f(u)

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

  • 0
    Draw the graph for this exercise, please2012-11-05
  • 0
    As you wish....2012-11-05
  • 0
    Thank you! but why the drawing is only f (u) and v?2012-11-05
  • 0
    The vertices $u$ and $v$ are arbitrary, provided that they belong to the same component and $f(u)$f(u)$ and $v$ matters, which is what I've drawn. – 2012-11-05