Let $G$ be a connected simple graph not having $P_4$ or $C_3$ as an induced subgraph Prove that $G$ is a biclique. Let $G$ be a connected simple graph not having $P_4$ or $C_3$ as an induced subgraph Prove that $G$ is a biclique.
I am looking for a proof that does not utilize induction.
 A: If $G$ has an odd cycle, let $C$ be one of minimal length $n$; clearly $n>3$. Let $v_1,v_2,v_3$, and $v_4$ be consecutive vertices of $C$; $G$ contains no triangle, so these vertices induce either a $P_4$ or a $C_4$. The former case is excluded by hypothesis. In the latter case we can replace the path $v_1v_2v_3v_4$ in $C$ by the edge $v_1v_4$ to get a cycle of length $n-2$, contradicting the minimality of $n$. Thus, $G$ cannot have an odd cycle and therefore must be bipartite. 
Let the parts of $G$ be $V_0$ and $V_1$, and suppose that there are $v_0\in V_0$ and $v_1\in V_1$ that are not adjacent. $G$ is connected, so let $P$ be a path of minimal length from $v_0$ to $v_1$, say $u_1=v_0,u_2,\ldots,u_{2n}=v_1$, where $n\ge 2$. Minimality of $P$ and the hypothesis that $v_0$ is not adjacent to $v_1$ imply that $u_{2n-3}$ is not adjacent to $u_{2n}=v_1$, so $u_{2n-3},u_{2n-2},u_{2n-1}$, and $u_{2n}$ induce a copy of $P_4$. This is impossible, so $G$ must be a biclique.

Note that if we further require that $G$ not contain $P_4$ as a subgraph at all, we can show that $G$ is a star. Fix a vertex $v$ of maximal degree. If $\deg v=1$, $G$ is $K_{1,1}$. Otherwise, let $u$ and $w$ be distinct vertices adjacent to $v$. $G$ does not contain $C_3$, so $u$ and $w$ cannot be adjacent. Suppose that $u$ is adjacent to some vertex $x$ other than $v$; then $wvux$ is a copy of $P_4$, which is impossible. Thus, $G$ is a star with centre $v$.
A: The girth of $G$ is $4$ or $\infty$. Suppose it is not. Then take the smallest cycle $c_1,c_2,c_3,c_4,c_5\dots c_k$. Then the induced subgraph on $c_1,c_2,c_3,c_4$ is not a $P_4$. So there is an edge between two non consecutive vertices. A contradiction since this creates a smaller cycle.
If the girth is $\infty$ $G$ has no cycles and no $P_4$, since it is connected it is a star.
If the girth is $4$, since it has no odd cycles it is bipartite, also notice both parts have at least two vertices.Assume it is not a biclique,take the shortest geodesic of even length in $G$ of length $4$ or more, call it $v_1,v_2\dots v_{2n}$. then $v_1,v_2,v_{2n-1},v_{2n}$ induces a $P_4$.
