# Graph

## Prove that complete graph K4 is planar

In this article, we will show that the complete graph K4 is planar. Complete Graph: A Complete Graph is a Graph in which all pairs of vertices are directly connected to each other.K4 is a Complete Graph with 4 vertices. Planar Graph: A graph is said to be a planar graph if we can draw …

## Prove that Petersen Graph is not Hamiltonian

In this article, we will prove that Petersen Graph is not Hamiltonian. Petersen Graph: A Petersen Graph is a cubic graph of 10 vertices and 15 edges. Each vertex in the Petersen Graph has degree 3. There is no 3-cycle or 4-cycle in the Petersen Graph. Hamiltonian Graph: A Hamiltonian Graph is a graph that …

## Show that Every Bipartite Graph is Perfect

In this article, we will show that every bipartite graph is perfect. Suppose a Bipartite Graph G(V, E). Let V1 and V2 be the sets such that every edge in G connects a vertex in V1 and a vertex in V2. Graph G is a perfect graph if, for every subgraph S, the clique number …

## Show that every bipartite graph is 2 chromatic

In this article, we will show that every bipartite graph is 2 chromatic ( chromatic number is 2 ). A simple graph G is called a Bipartite Graph if the vertices of graph G can be divided into two disjoint sets – V1 and V2 such that every edge in G connects a vertex in …