Graph

5 Color Theorem

According to 5 Color Theorem, every planar graph is 5 colorable. Lemma: Every planar graph is 6 colorable. This is also known as 6 Color Theorem. Proof of 5 Color Theorem We will prove it by mathematical induction. Step 1Every planar graph vertices is 5 colorable. Step 2Assume every planar graph vertices is 5 colorable. …

5 Color Theorem Read More »

6 Color Theorem

According to 6 Color Theorem, every planar graph is 6 colorable. Lemma: For any simple planar graph G, the minimum degree is less than equal to 5. Proof: The average degree D of a graph is . We know that every planar graph satisfies the equation . On substituting the equations, we getThus, the average …

6 Color Theorem Read More »

Prove that a bipartite graph has a unique bipartition if and only if it is connected

In this article, we will show that a bipartite graph has a unique bipartition if and only if it is connected. Bipartite Graph: A Graph is bipartite if we can divide its vertices into two disjoint sets, V1 and V2 such that no edge connects vertices from the same set. Unique Bipartition: Unique Bipartition means …

Prove that a bipartite graph has a unique bipartition if and only if it is connected Read More »