Before proof, we will define some basic terminologies.
Bipartite Graph: A graph whose vertices can be divided into 2 disjoint sets such that no two vertices in the same set are adjacent to each other is called Bipartite Graph.
Proof
We can prove the given statement by contradiction. Suppose you have a bipartite graph G. Let V1 and V2 be the bipartitions of G.
Suppose there is a triangle in the graph. The triangle is shown below:-
Since the graph is bipartite, we should be able to divide vertices – a, b, and c in set V1, V2 such that no two vertices are adjacent to each other. But this is not possible. We cannot separate a, b, c without atleast 2 of them being in the same set.
For example, put vertex a in V1 and vertex b in V2. Now if we put vertex c in V1 or V2, it will violate bipartite property since c is adjacent to both a and b. Therefore, graph G cannot be bipartite.
Therefore, our assumption that a bipartite graph contains a triangle is incorrect. Thus, we can say that a graph that contains a triangle cannot be bipartite.
Read