Graph

Wheel Graph

A wheel graph is obtained by connecting a vertex to all the vertices of a cycle graph. It is denoted by Wn, for n > 3 where n is the number of vertices in the graph. A wheel graph of n vertices contains a cycle graph of order n – 1 and all the vertices …

Wheel Graph Read More »

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 »