# Discrete mathematics

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

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