Types of Graphs

There are various types of graphs in graph theory, some of these are:

• Null Graph
• Trivial Graph
• Simple Graph
• Undirected Graph
• Directed Graph
• Weighted Graphs
• Complete Graph
• Bipartite Graphs

Let’s discuss these types in detail as follows:

Null Graph

A null graph, also known as an empty graph, is a type of graph in which the vertex setV is non-empty, but the edge set E is empty.

In other words, a null graph has vertices but no edges connecting any pairs of vertices.

Consider a null graph with three vertices:

• Vertex set V: {A, B, C}
• Edge set E: { } or ϕ

Note: Each vertex in a null graph has a degree of zero, since there are no edges connected to any vertex.

Trivial Graph

A trivial graph is the simplest type of graph, consisting of exactly one vertex and no edges.

Consider a trivial graph with one vertices:

• Vertex set V: {A}
• Edge set E: { } or ϕ

Simple Graph

A simple graph is a type of graph in which each pair of vertices is connected by at most one edge, and no vertex has an edge to itself.

This means that a simple graph does not contain any loops (edges that connect a vertex to itself) or multiple edges between the same pair of vertices.

Consider a simple graph with four vertices:

• Vertex set V: {A, B, C, D}
• Edge set E: { {A, B}, {A, C}, {B, D}, {C, D} }

Undirected Graph

An undirected graph is a type of graph in which the edges have no direction.

This means that the relationship between any pair of connected vertices is mutual. In an undirected graph, the edge (u, v) is identical to the edge (v, u).

Consider an undirected graph with four vertices:

• Vertex set V: {A, B, C, D}
• Edge set E: { {A, B}, {A, C}, {B, D}, {C, D} }

Directed Graph

A directed graph, also known as a digraph, is a type of graph where the edges have a direction.

In other words, each edge has a starting vertex (source) and an ending vertex (destination), indicating a one-way relationship between the vertices.

Consider a directed graph with four vertices:

• Vertex set V: {A, B, C, D}
• Edge set E: { (A, B), (A, C), (B, D), (C, D)}

Weighted Graphs

A weighted graph is a type of graph in which each edge is assigned a weight (or cost).

These weights can represent various quantities such as distances, costs, capacities, or any other metric that quantifies the relationship between vertices.

Consider a weighted graph with four vertices

• Vertex set V: {A, B, C, D}
• Edge set E: { (A, B, 3), (A, C, 5), (B, D, 2), (C, D, 1) }

Complete Graph

If every vertex in a graph G is linked to every other vertex in the graph, then the graph is said to be complete. Therefore, every graph G has to be linked. K_n represents the whole graph with n vertices.

Consider a complete graph with four vertices:

• Vertex set V: {A, B, C, D}
• Edge set E: { {A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D} }

Note: Number of Edges in complete graphs with n vertices is n(n – 1)/2.

Bipartite Graphs

A bipartite graph is a type of graph where the vertex set can be divided into two disjoint sets such that no two vertices within the same set are adjacent.

This means that every edge in a bipartite graph connects a vertex in one set to a vertex in the other set.

Consider a bipartite graph with vertex sets:

• Vertex sets V₁​: {A, B}, V₂​: {C, D}
• Edge set E: { {A, C}, {A, D}, {B, C} }

Cycle Graph

A cycle graph, also known as a circular graph, is a type of graph that forms a single cycle.

In a cycle graph, each vertex has exactly two neighbors, creating a closed loop.

Consider a cycle graph C₄​ with four vertices:

• Vertex set V: {A, B, C, D}
• Edge set E: {{A, B}, {B, C}, {C, D}, {D, A} }

Graph theory is a branch of mathematics that studies the properties and applications of graphs. A graph is a collection of vertices (also called nodes) connected by edges (also called links). Graphs are used to model pairwise relations between objects, making them a powerful tool for representing and analyzing complex systems in various fields.

In this article, we will discuss all the fundamentals of graph theory, from its definition to its types, and various ways to represent graphs as well.