# Graph

## Hamiltonian Graph

Hamiltonian Graph is a connected graph that contains a Hamiltonian Circuit. It means there exists a cycle in the graph that visits each vertex exactly once.

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

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

## Prove every tree is planar

Prove that every tree is planar. We can prove every tree is planar by using Euler’s formula or by mathematical induction.

## Prove hypercube is hamiltonian

In this article, we will prove that every hypercube is hamiltonian. Hamiltonian: A graph is Hamiltonian if it contains a Hamiltonian circuit. It means there exists a cycle in the graph that visits each vertex exactly once. Hypercube: It is denoted by Qn. It contains 2n vertices and the degree of each vertex is n.Each …

## Prove that every tree is a bipartite graph

In this article, we will show that every tree is a bipartite graph. Tree: A tree is a simple graph with N – 1 edges where N is the number of vertices such that there is exactly one path between any two vertices. Bipartite: A graph is bipartite if we can divide the vertices into …

## Show that a graph is bipartite if and only if it does not have a cycle of odd length

In this article, we will prove that a graph is bipartite if and only if it does not have a cycle of odd length. First, we will prove that if a graph is bipartite then it doesn’t have a cycle of odd length. Proof We will prove this by contradiction. Suppose a Bipartite Graph G(V, …

## 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 Hypercube is Bipartite

In this article, we will show that every hypercube (Qn) is bipartite. Bipartite: A Graph is Bipartite if we can divide the vertices of the graph into two sets such that no two vertices in the same set are adjacent to each other. Hypercube: A Hypercube is denoted by Qn. A hypercube has 2n vertices …

## Prove that Petersen Graph is nonplanar

In this article, we will show that Petersen Graph is non-planar. Petersen Graph: Petersen Graph is a Cubic Graph with 10 vertices and 15 edges such that each vertex has degree 3. There is no 3-cycle or 4-cycle in the Petersen Graph. Non-planar Graph: A graph is called a non-planar graph if it is impossible …