# Complete Bipartite Graph

I am trying to do this problem, but I don't see how it could be true. I think I have a counter example, but I am looking for confirmation.

$P_n$ is the graph which is a path of length n. $C_n$ is the graph which is a cycle of length n.

Let $G$ be a connected simple graph not having $P_4$ or $C_3$ as an induced subgraph. Prove that $G$ is a biclique (complete bipartitie graph).

However, isn't $C_5$ a counter example to this problem? It clearly is connected simple graph. It doesn't contain $C_3$. And to have a path of length 4, we would need 5 verticies, but that would give us the cycle not the path.

-
I think $P_n$ and $C_n$ should mean a path and a cycle with $n$ vertices. –  dtldarek Apr 20 '12 at 9:57
Don't all connected simple graphs $G$ with $n\ge 4$ vertices have $P_n$ as (vertex?-)induced subgraph? –  draks ... Apr 20 '12 at 10:30
@draks: No, consider an $n$-star. It has $P_3$ as an induced subgraph, but not $P_4$. For the original question: That is a matter of convention. I think dtldarek is right, $P_n$ should be the path with $n$ vertices. Then, obviously, $P_4$ is an induced subgraph of $C_5$. –  m_l Apr 20 '12 at 10:58

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.

-
Everyone defines $P_n$ to be the path with $n$ vertices, not just Wikipedia. –  Graphth Apr 20 '12 at 15:05
@Graphth: Well, everyone except the OP :-) –  joriki Apr 20 '12 at 15:14
Thanks! I guess I misunderstood $P_n$. –  Danikar Apr 20 '12 at 15:34

I think the following proof works, ignore if you didn't want to see attempts at a proof but only regarding the question about $C_5$ specifically:

You can prove this by induction. Any connected simple graph of 2 vertices is a biclique. Suppose that for k <= n, any connected simple graph with k vertices not having $P_4$ or $C_3$ as an induced subgraph has this property. Now consider any graph of size n+1 that does not have either $P_4$ or $C_3$ as an induced subgraph. Then for any vertex v, the subgraph induced on all other vertices is a biclique (since it does not have $P_4$ or $C_3$ as an induced subgraph). Since the graph (call it G) is connected, there is a vertex w which is adjacent to v (in the induction case n>2). Call the partition of vertices to which w belongs in the n-sized induced subgraph (which is a biclique) $p_1$ and the other one $p_2$. Consider any vertex x in $p_2$. Since there is a vertex wx (by induction hypothesis), vx does not exist (else $C_3$ would become an induced subgraph). For any vertex other than v in $p_1$ (say y), xy also exists. If vy does not exist, then the path vwxy would induce $P_4$ in the subgraph of G consisting of v, w, x, y. So vy must also exist.

EDIT: As joriki pointed out, the subgraph induced on the rest of the vertices need not be connected. In that case, all we know for now is that each connected component of the subgraph induced on the rest of the vertices is a biclique, with the added condition that for each of these components there exists a vertex which has an edge to v.

Let $G_1$ and $G_2$ be two such components, with vertex w and x repectively that is connected to v. If removal of v splits G into isolated points, then G is already a biclique (one partition being v itself and other one being rest of vertices). Else, at least one out of $G_1$ and $G_2$ has at least one more vertex in addition to the one that is connected to v. Without loss of generality, we can assume this is $G_1$, and let the vertex be y. Now we know that ywvx is a connected path. yx and wx cannot exist as x is on a different connected component from y and w. vy does not exist as then ywv will be a triangle. So the subgraph og G induced on y,w,v,x will then be $P_4$. So we can safely rule out this situation too.

-
The subgraph induced on all other vertices need not be connected, but that would be required to apply the induction hypothesis? –  joriki Apr 20 '12 at 11:29
You are right, I have to rule it out. Editing accordingly. –  Wonder Apr 20 '12 at 11:31
$G$ not being $P_3$ doesn't imply that at least one of $G_1$ and $G_2$ has more than one vertex. Removing $v$ could split $G$ into isolated vertices. –  joriki Apr 20 '12 at 11:41
That graph would also be a biclique, so it doesn't change things much... I edited it accordingly. –  Wonder Apr 20 '12 at 11:50
Anyway the claim only holds if $P_n$ is the path with n vertices, not n edges, as you pointed out. –  Wonder Apr 20 '12 at 11:52