If $G$ is triangle-free does that imply it is a complete bipartite graph?

863 Views Asked by At

If $G$ is triangle-free does that imply it is a complete bipartite graph?

I know every bipartite graph is triangle free, and any complete bipartite graph has no triangles but does a graph being triangle free imply it's a complete bipartite graph? Also, are the independent sets in the triangle free graph (if the above is true) equal?

2

There are 2 best solutions below

2
On BEST ANSWER

Trivially no. If you remove edges from a triangle-free graph then you get another triangle-free graph, whereas if you remove edges from a complete bipartite graph you get a graph which is bipartite but not complete. Therefore this could only be the case if all triangle-free graphs were edgeless.

1
On

Try thinking about cycles longer than $3$ or $4$. For example $C_5$ and $C_6$ are triangle free, but $C_5$ isn't even bipartite, and $C_6$ isn't complete bipartite.