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