Let $G$ be a connected graph not having $P_4$ or $C_3$ as an induced subgraph. Prove that $G$ is a complete bipartite graph.
I understand what a complete bipartite graph is but am not sure how to relate that to a $P_4$ graph.
[Math] Prove that a connected graph not having $P_4$ or $C_3$ as an induced subgraph is complete bipartite
discrete mathematicsgraph theory
Related Solutions
If $P_n$ denotes the path graph with $n$ edges, your counterexample is right and the claim is wrong. We could consider whether the claim becomes right if we leave out "induced", since that would eliminate your counterexample, but even then the claim is wrong: Consider a graph with two central vertices joined by an edge and any number of vertices joined to either of the two by a single edge. This simple graph is connected and contains neither $C_3$ nor $P_4$ as a subgraph but is clearly not a biclique.
However, Wikipedia defines $P_n$ to be the path graph with $n$ vertices. In that case, the claim is true. If there are two vertices at distance $\ge3$, then there are two vertices at distance $3$. But then the subgraph induced by the four vertices of any minimal path connecting them would be $P_4$. Thus all distances in the graph are $\le2$. Pick some vertex $v$ and consider the set $S$ of vertices formed by $v$ and all vertices at distance $2$ from $v$. There is no edge between $v$ and any other of the other vertices in $S$. If any two other vertices in $S$, say $w$ and $x$, were connected by an edge, there would have to be either an induced $C_3$ or an induced $P_4$ in the subgraph of $5$ vertices induced by $v$, $w$, $x$ and two vertices between $v$ and $w$ and between $v$ and $x$. Thus no two of the vertices in $S$ are connected by an edge. Also no two vertices in the set $T$ of vertices at distance $1$ from $v$ are connected by an edge, since that would result in an induced $C_3$. It follows that all vertices in $S$ are connected by an edge to all vertices in $T$, since otherwise the missing connections would have to be supplied by paths of length $\gt2$. Thus the graph is a complete bipartite graph.
First, we claim that $G$ is connected. Suppose, on the contary, that two vertices $u$ and $v$ are in different components. Since $u$ and $v$ are not isolated, there is a vertex $u'$ adjacent to $u$ and a vertex $v'$ adjacent to $v$. Now consider the induced subgraph on $\{u,u',v,v'\}$; it contains the edges $uu'$ and $vv'$, but by assumption it must not contain only two edges, so it must contain another edge, either $uv$, $uv'$, $u'v$, or $u'v'$, which in any case violates our assumption that $u$ and $v$ are in different components. Therefore $G$ is connected.
Suppose that $G$ is not a complete graph. Let $A$ be a maximal complete subgraph of $G$, and let $u$ be an vertex of $G$ not in $A$. Without loss of generality, we can assume that $u$ is adjacent to a vertex $a \in A$. (Proof: Choose an arbitrary vertex $a\in A$; since $G$ is connected, there is a path from $a$ to $u$, and along this path let $a'$ be the last vertex in $A$, and let the next vertex along the path be $u'$. Then $u' \notin A$, so by replacing $a$ and $u$ by $a'$ and $u'$ respectively, we may assume that $u$ is adjacent to $a$.) Now let $b$ be any vertex in $A$ distinct from $a$, and consider the induced subgraph on $\{a,b,u\}$. We are assuming that the edge $au$ is in $G$, and since $a,b\in A$ and $A$ is a complete graph we also have $ab$ in $G$; but since the induced subgraph cannot contain exactly two edges, we must also have $bu$ in $G$. Thus $u$ is a adjacent to every vertex in $A$, so $A\cup\{u\}$ is a complete subgraph, contradicting the maximality of $A$. This completes the proof.
Best Answer
$P_4$ must mean a $4$-vertex path (a path of length $3$), otherwise the claim is not true; the $5$-vertex cycle is a counter-example.
Let $C$ an odd cycle of smallest length (if any) in $G$. If $c \geq 5$ then any chord (edge in $G \setminus C$ connecting two vertices in $C$) implies...
Hence $C$ (if it exists) is an induced subgraph, and thus $C$ (and hence $G$) contains an induced $P_4$ subgraph, giving a contradiction. Hence $C$ does not exist.
Hence $G$ contains no odd length cycles, and is thus is a connected subgraph of $K_{n,m}$ for some $n,m$. Let the parts be denoted $N$ and $M$.
If $u \in N$ and $v \in M$, then the shortest path between $u$ and $v$ is...
Hence $G=K_{n,m}$.