Graph

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 »

Prove that a bipartite graph with an odd number of vertices is not hamiltonian

First we will define some basic terminologies. Bipartite Graph: A graph is bipartite if we can spit the vertices of the graph in two distinct sets V1 and V2 such that no edge connects vertices belonging to the same set. Hamiltonian Graph: A graph is hamiltonian if it contains a hamiltonian circuit. Hamiltonian circuit is …

Prove that a bipartite graph with an odd number of vertices is not hamiltonian Read More »

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 »