## Introduction

This is the second article in the Graph Theory – Online Classes.

Dear readers, I assume that you have already finished reading the first post, if not I would advise you to please go through the first article in the series Introduction to Graph Theory, as this post will require some basic knowledge which we discussed in the previous post.

## Few Special Graphs

**The Null Graph**

The first graph we will discuss is the Null Graph. By definition, this graph has a V(G) which is non-empty and a E(G) which is empty. In simple words a graph which only has vertices and no edges is a Null Graph.

Few points about Null Graph.

- A Null Graph is represented using the symbol N
_{n}where n is the number of vertices. - In a Null Graph, every vertex is isolated.
- A N
_{n}is always a totally disconnected graph if n is greater than 1. - Number of vertices in such a graph is always
**n.** - Number of edges in such a graph is always
**zero.**

The Graph 1 in the below image is a Null Graph N_{4}.

**The Complete Graph**

For a simple graph to be a complete graph, it is important that every pair of its distinct vertices are adjacent to each other. In simple words, each vertex is connected to the remaining vertices.

Few points about Complete Graph.

- A Complete Graph is represented using the symbol K
_{n}where n is the number of vertices. - In a Complete Graph, every vertex is connected to every other vertex, which means in K
_{n}every vertex is connected to n-1 vertices, this also means that there are n-1 edges connected to each vertex. - Number of vertices in such a graph is always
**n**. - Number of edges in such a graph is always
**1/2 * n * (n – 1)**. As we stated above there are n vertices and each connects to n-1 remaining vertices so the number of edges is the product of n and n-1, but remember that by doing this we count each edge two times once for each vertex which is incident on the edge. So we half the count to get exact number of edges.

The Graph 2 in the above image is a Complete Graph K_{4}.

**The Regular Graph**

The graph G is a regular graph if all its vertices have the same degree. For e.g. if the degree of a vertex in G is r, then the graph G is said to be regular of degree r.

Few points about the Regular Graph.

- An example of regular graph is the Null Graph N
_{n}. All such graphs are regular in degree**zero**. - Another example of regular graph is the Complete Graph K
_{n}. All such graphs are regular in degree**(n-1)**. - If G has n vertices and it is regular in degree r then G has
**1/2 * n * r**. Refer the above explanation for number of edges in Complete Graph.

**The Bipartite Graph**

The graph G is said to be a Bipartite graph if G(V), the vertex set can be divided into two subsets V_{1} and V_{2} such that if there exists an edge in the graph, it connects one vertex from each of the sets.

Few points about the Bipartite Graph.

- A Bipartite Graph can be represented as K
_{m,n}where m is the number of vertices in set V_{1}and n is the number of vertices in set V_{2}. - The above point deduces the fact that the total number of vertices in the Bipartite graph is
**m + n** - The maximum number of edges in such a graph would be
**m * n**

Below is an image of K_{3,4}. Notice that in a Bipartite Graph, it is **not** necessary that each vertex from V_{1} should connect to each vertex in V_{2}. Assume that the blue vertices are in set V_{1} and the red vertices are in set V_{2}

For more on Bipartite Graphs, please refer Wikipedia

**The Complete Bipartite Graph**

The Bipartite Graph G is said to be a Complete Bipartite Graph each vertex in V_{1} is connected to each vertex in V_{2}.

Below is an image of K_{3,4} which is a Complete Bipartite. Assume that the blue vertices are in set V_{1} and the red vertices are in set V_{2}

**Note:** Similar to Bipartite Graphs there can be Tripartite Graphs as well. That will have three disjoint sets of vertices. May be V_{1}, V_{2} and V_{3} and rest all the conditions remain same as Bipartite graphs.

**The k-Cubes Graph**

This graph belongs to the family of Bipartite Graphs. This graph is represented by Q_{k} and it is such that its vertices correspond to a binary sequences of length k. Which means that the vertices of Q_{3} will correspond to {000, 001, 010, 011, 100, 101, 110, 111}.

Each of the vertices can be represented by one of the entries in the above set and only those vertices can be connected to each other whose sequence differs just by 1 by one bit.

Few points about the k-Cube Graph.

- The graph will always be a regular graph of degree k. As each of the vertices will have exactly k vertices to connect to because there are k bit sequences and each bit has a possibility to change. For e.g. in Q
_{3}the vertex corresponding to 000 can connect to vertices corresponding to all these sequences {001, 010, 100} - The total number of vertices in the Q
_{k}Graph is**2**.^{k} - The total number of edges in the Q
_{k}Graph is**1/2 * k * 2**. We arrived at this calculation because each vertex is of degree k and there are total 2^{k}^{k}vertices, so the total number of edges would be the product of degree and number of vertices. But in this calculation we counted each edge for exactly two vertices which are incident on the edge, so we take half of the final numbers.

We can generalize our understanding for Q_{k}.

Below is an image of Q_{3.
}

Here is the Bipartite representation of the above Q_{3} graph.

We end up this post here with some knowledge of special graphs which are of major importance. In subsequent articles these graphs will be referred many times.

**Do not forget to subscribe with your email to receive latest posts on Graph Theory.**