# Graph

## Prove that Every 2-Connected Graph Contains at least One Cycle

In this post, we will be show how every 2-connected graph contains atleast one cycle. First, we will discuss what exactly is a 2-connected graph. A connected graph is said to be 2-connected if it contains more than 2 vertices and the graph remains connected if fewer than 2 vertices are removed from the 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 …

## Hierholzer’s Algorithm

Hierholzer’s algorithm is another algorithm to find the Euler Path or Euler circuit in a graph. It’s time complexity is O(E).

## Fleury’s algorithm

Fleury’s algorithm is used to find a Euler Path/Circuit in a connected graph. It is based on the principle that the bridge edge is visited in last.

## Euler Path and Euler Circuit

A circuit that visits every edge exactly once is known as Euler Circuit. A path that visits every edge of a graph exactly once is known as Euler Path.

## Bipartite Graph

A simple graph is called Bipartite if it’s vertices can be partitioned into two disjoint sets, such that no edge connects vertices of same set.

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