## Prove that a graph which contains a triangle cannot be bipartite

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. …

Prove that a graph which contains a triangle cannot be bipartite Read More »