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 …
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, …
Show that a graph is bipartite if and only if it does not have a cycle of odd length Read More »
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 a bipartite graph has a unique bipartition if and only if it is connected Read More »
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 …
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 …
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 …
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 …
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 …
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 …