Proof: A Graph or its Complement is not Bipartite | Graph Theory, Bipartite Graphs

If G is a graph with at least 5 vertices, at most one of G or G complement is bipartite. We will prove this graph theory result directly using the well know bipartite graph theorem relating to odd cycles.

The only way the statement is false is if there exists a graph G of order 5 or more such that G and G complement is bipartite. So we assume a graph G is bipartite, and show that G complement must have an odd cycle and thus cannot be bipartite. We do not have to prove that if G complement is bipartite then G is not, because the graph G is arbitrary, and G complement relates to G in the same way that G relates to G complement - they are complements of each other.

Lesson proving a bipartite graph has no odd cycles:

Lesson proving a graph with no odd cycles is bipartite:



I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:

Follow Wrath of Math on...
● Instagram:
● Facebook:
● Twitter:

My Music Channel:

wrath of math,math lessons,math,education,math video,graph theory,bipartite graphs,graph or its complement is not bipartite,bipartite graph proof,