A good understanding of graphs is important for understanding algorithms and graphical approaches such as probabilistic graphical models in machine learning. In this article, we will familiarize with the essential concepts in Graph Theory.
A graph is a discrete structures that consist of vertices connected by edges.
The set of all vertices in a graph is denoted by \( V \). Each edge is an unordered pair \( \set{a,b} \) for some \(a, b \in V \). The set of all such edges is denoted by \( E \). Thus, a graph can be defined as \( G = (V,E) \).
Vertices \( a \) and \( b \) are said to be adjacent or neighbors if they are connected by an edge \( \set{a,b} \in E \). The edge is known as incident with the verticies \( a \) and \( b \). The vertices \( a \) and \( b \) are known as the endpoints of the edge.
In a simple graph, there is at most one edge between any pair of vertices. Moreover, loops, or an edge from a vertex to itself is not allowed in a simple graph.
This means, if \( G = (V,E) \) is a simple graph, then there are no duplicate unordered pairs in \( E \) and for all \( (v_i, v_j) \in E \), it is the case that \( v_i \ne v_j \).
Multigraphs allow for multiple edges between the same pair of vertices. It means, there could be duplicate unordered pairs in set \( E \) of the graph \( G = (V,E) \). Loops (edges connecting a vertex with itself) are not permissible in a multigraph
Pseudographs are a further extension that allow for multiple edges between the same pair of vertices and also allow for loops.
Thus, pseudographs are the most general type of undirected graphs because they contains loops and multiple edges.
The complementary graph of a graph \( G = (V,E) \) is a graph with the same vertices, but with edges that do not appear in the graph G. It is denoted as \( \overline{G} \).
Thus, two vertices are adjacent in \( \overline{G} \) if and only if they are not adjacent in \( G \).
In directed graphs, each edge consists of an ordered pair of vertices \( (a, b) \) such that there is a directed edge from the vertex \( a \) to the vertex \( b \).
The vertex \( a \) is said to be adjacent to the vertex \( b \). The vertex \( a \) is also known as the initial vertex of the edge.
Conversely, the vertex \( b\) is said to be adjacent from the vertex \( a \). The vertex \( b \) is also known as the terminal vertex or end vertex of the edge.
In directed multigraphs, there could be multiple directed edges from a vertex \( a \) to a vertex \( b \).
The converse of a directed graph \( G = (V,E) \) is denoted as \( \complement{G} \) and contains the same vertices but the edges are reversed in direction.
Thus, if there is an edge from a vertex \( a \) to a vertex \( b \) in \( G \), then in its converse, there will be an edge from \( b \) to \( a \).
The degree of a vertex in an undirected graph is the number of edges incident with it. Each loop at the vertex contributes twice to the degree of that vertex. The degree of a vertex \( v \) is denoted as \( \text{deg}(v) \).
A vertex with degree one is known as a pendant.
In a directed graph, there is a distinction between the count of edges reaching a vertex and those leaving it. The in-degree of a vertex, denoted by \( \text{deg}^-(v) \) is known as the number of edges reaching vertex \( v \). Or, the number of edges that have the vertex \( v \) as their terminal vertex.
The out-degree of a vertex, denoted by \( \text{deg}^+(v) \) is known as the number of edges starting from the vertex \( v \). Or, the number of edges that have the vertex \( v \) as their initial vertex.
Each loop at a vertex in a directed graph contributes one to its in-degree and one to its out-degree.
A simple graph is known as a regular graph if every vertex has the same degree. If each vertex has a degree \( n \), then it is known as an \( n \)-regular graph.
Let \( G = (V,E) \) be an undirected graph with \( e \) edges. Then
$$ 2e = \sum_{v \in V} \text{deg}(v) $$
This means, that the sum of the degrees of all vertices in a graph is equal to twice the number of edges in the graph. This is easy to prove, because each edge contributes to the degrees of two vertices. Note that this applies even if multiple edges and loops are present in the graph.
In a graph with \( 8 \) vertices, each with degree \( 5 \), there are exactly \( e \) edges, such that \( 2e = 8 \times 5 \). Thus, due to the handshake Theorem, \( e = 20 \).
An undirected graph has an even number of odd-degree vertices.
Suppose \( V_o \) and \( V_e \) denote the set of vertices of odd and even degrees respectively. Let \( V \) denote the set of all vertices of the graph and \( V = V_o \cup V_e \).
Then, by the handshaking Theorem, if \( e \) is the number of edges, we know that
$$ 2e = \sum_{v \in V} \text{deg}(v) = \sum_{v \in V_e} \text{deg}(v) + \sum_{v \in V_o} \text{deg}(v) $$
The left hand side of the above equation is clearly even. So, the right hand side must be even too.
The first term on the right hand side is even, because the degree is even for each of the vertices in \( V_e \). Therefore, the second term on the right hand side must be even too. Now, the degrees of each of the vertices in \( V_o \) is odd. So, the number of such vertices must be even for the equation to hold.
Thus, there are even number of vertices of odd-degree in an undirected graph.
In a directed graph, each edge has a initial vertex and a terminal vertex. Since every edge contributes equally to the in-degree and the out-degree, it is the case that the sum of the in-degree of all vertices in a graph is equal to the sum of the out-degree of all vertices.
For a graph \( G = (V,E) \),
$$ \sum_{v \in V} \text{deg}^- (v) = \sum_{v \in V} \text{deg}^+ (v) $$
A graph with exactly one edge between every pair of distinct vertices is known as a complete graph. A complete graph with \( n \) vertices is usually denoted by \( K_n \).
A graph with \( n \) vertices, \( v_1, v_2, \ldots, v_n \) is known as a cycle if it contains exactly the edges \( \set{v_1,v_2}, \set{v_2,v_3}, \ldots, \set{v_{n-1},v_n}, \set{v_n,v_1} \) going around a full cycle connecting all the vertices of the graph. A cycle graph with \( n \) vertices is usually denoted by \( C_n \).
In this interactive demo, we will study the nature of cycle graphs and their various isomorphisms.
Wheels are an extension of a cycle with an additional vertex that is connected to all the other vertices. Thus, a wheel is a graph with \( n \) vertices, \( v_1, v_2, \ldots, v_n \) such that the first \( n-1 \) vertices form a cycle with the edges \( \set{v_1,v_2}, \set{v_2,v_3}, \ldots, \set{v_{n-2},v_{n-1}} \). The final vertex \( v_n \) is connected to all the other vertices with the edges \( \set{v_1,v_n}, \set{v_2,v_n}, \ldots, \set{v_{n-1},v_n} \).
A wheel graph with \( n \) vertices is usually denoted by \( W_n \).
In this interactive demo, we will study the nature of wheel graphs and their various isomorphisms.
There are \( 2^n \) bit strings of length \( n \). Imagine that each such bit-string represents a vertex in a graph. An \(n\)-cube graph is a graph containing such \( 2^n \) vertices such that there is an edge between two vertices if the bit-string representing them differs by a single bit.
An \(n\)-cube graph with \( n \) vertices is usually denoted by \( Q_n \).
A simple graph \( G = (v,E) \) is called a bipartite graph if its vertices can be partitioned into two disjoint nonempty sets \( V_1 \) and \( V_2 \) such that every edge in the graph connects some vertex in \( V_1 \) to some vertex in \( V_2 \). Thus, there are no edges connecting two vertices \( V_1 \) or two vertices in \( V_2 \).
Suppose, the vertices of a bipartite graph can be partitioned into two disjoint nonempty sets \( V_1 \) and \( V_2 \) such that every edge in the graph connects some vertex in \( V_1 \) to some vertex in \( V_2 \) and there are no edges connecting two vertices in \(V_1\) or two vertices in \( V_2 \). If furthermore, each vertex in \( V_1 \) is connected to all vertices in \( V_2 \), then the bipartite graph is known as a complete bipartite graph.
A complete graph with \( m \) vertices in one set and \( n \) in the other set of the partition is usually denoted by \( K_{m,n} \).
When some edges and corresponding vertices are removed from a graph without removing the endpoints of the remaining edges, we get a smaller graph that is known as subgraph of the original graph.
Thus, a subgraph of a graph \( G = (V,E) \) is a graph \( H = (W,F) \) such that \( W \subseteq V \) and \( F \subseteq E \).
A complete subgraph of a graph that is not contained within a larger complete subgraph is known as a clique.
The union of two simple graphs \( G_1 = (V_1, E_1) \) and \( G_2 = (V_2, E_2) \), is another graph \( G = (V, E) \), such that \( V = V_1 \cup V_2 \) and \( E = E_1 \cup E_2 \).
The union operation on graphs is usually denoted as \( G = G_1 \cup G_2 \).
In an adjacency list representation of a graph, each vertex in the graph is accompanied with a list of all of its adjacent vertices in the graph.
Consider a graph \( G = (V,E) \) where \( V = \set{a, b, c} \) and \( E = \set{ \set{a,b}, \set{b,c}} \).
For this graph, the adjacency list will feature
Consider a graph \( G = (V,E) \) with \( n \) vertices, \( v_1, v_2, \ldots, v_n \).
Imagine an \( n \times n \) matrix \( \mat{A}_G \) consisting of 0s and 1s such that its \( (i,j)\)-th entry is 1 if there is an edge \( \set{v_i,v_j} \in E \) and 0 otherwise. Such a matrix \( \mat{A}_G \) encodes all information in the graph \( G \) and is known as its adjacency matrix representation.
Since the adjacency matrix representation relies on the ordering of the vertices, there are \( n! \) possible adjacency matrices for a graph with \( n\) vertices for the \( n! \) ordering of these vertices.
As an alternative to the adjacency matrix representation, a common way to represent undirected graphs is the incident matrix representation.
A graph \( G = (V,E) \), with \( n \) vertices and \( m \) edges is represented with a \( n \times m \) matrix \( \mat{M}_G \) such that the \( ij \)-th entry of the matrix is 1 if the edge \(e_j \) is incident with the vertex \( v_i \), else it is 0.
If two graphs have exactly the same form, such that there is a one-to-one correspondence between their vertex sets that preserve the edges, then they are known are said to be isomorphic.
Mathematically, the simple graphs \( G_1 = (V_1, E_1) \) and \( G_2 = (V_2, E_2) \) are isomorphic if there is a one-to-one and onto function \( f \) from \( V_1 \) to \( V_2 \) with the property that the vertices \( a \) and \( b \) are adjacent in the graph \( G_1 \) if and only if the vertices \( f(a) \) and \( f(b) \) are adjacent in the graph \( G_2 \), for all \( a \) and \( b \) in \( V_1 \). The function \( f \) is known as an isomorphism.
Detecting isomorphic graphs is an important field of study in graph theory. Comparing all possible \( n! \) representations of \( n \) node graphs is infeasible.
Isomorphism is usually detected by comparing some properties of the graphs that will remain the same among isomorphic graphs. These are known as invariant properties. Some examples of invariant properties are
If a graph \( G \) and its complementary graph \( \overline{G} \) are isomorphic, then the graph is said to be self-complementary.
A path of length \( n \) from a vertex \( a \) to a vertex \( b \) in a graph is a sequence of edges \( e_1, e_2, \ldots, e_n \) such that the initial vertex of \( e_1 \) is \( a \) and the terminal vertex of \( e_n \) is \( b \). A path that starts and ends at the same vertex is known as a circuit
In a simple graph, a path may simply be denoted by the sequence of vertices it passes through. The path is then said to traverse the vertices \( v_1, v_2, v_{n-1} \) on its way from \( a \) to \( b \). A circuit is simple if it does not contain the same edge more than once.
An undirected graph is said to be connected if there is a path between every pair of distinct vertices of the graph.
An undirected graph that is not connected is the union of two or more connected subgraphs, each pair of which has no vertex in common. These disjoint connected subgraphs are called connected components of the graph.
If the removal of a vertex results in a connected graph not being connected anymore, then the vertex is known as a cut vertex or an articulation point.
Similarly, if the removal of an edge disconnects a connected graph, then it is known as a cut edge or a bridge.
In directed graphs there are two kinds of connectedness
Let \( \mat{A} \) denote the adjacency matrix of the graph \( G \) for some ordering of its vertices \( v_1, v_2, \ldots, v_n \). The number of different paths of length \( r \) between vertices \( v_i \) and \( v_j \), where \( r \) is a positive integer, equals the \( (i,j) \)th entry of the matrix \( \mat{A}^r \).
An Euler circuit in a graph \( G \) is a simple circuit containing every edge of the graph \( G \). A connected multigraph has an Euler circuit if and only if each of its vertices has even degree.
Similarly, an Euler path in \( G \) is a simple path containing every edge of \( G \). A connected multigraph has an Euler path, but not an Euler circuit, if and only if it has exactly two vertices of odd degree.
A Hamilton path is a path in a graph that passes through all the vertices of the graph exactly once. Thus, a path \( x_0, x_1, \ldots, x_{n-1}, x_n \) in the graph \( G = (V,E) \) is called a Hamilton path if \( V = \set{x_0,x_1,\ldots,x_{n-1},x_n} \) and \( x_i \ne x_j \) for \( 0 \le i < j \le n \). Similarly, a Hamilton circuit is a circuit \( x_0, x_1, \ldots, x_{n-1}, x_n, x_0 \) in a graph \( G = (V,E) \) if \( x_0, x_1, \ldots, x_n \) is a Hamilton path.
If \( G \) is a connected simple graph with \( n \) vertices, where \( n \ge 3 \), then \( G \) has a Hamilton circuit if the degree of each vertex is at least \( n/2 \).
An elementary subdivision is an operation that involves removing an edge \( \set{u,v} \) from a graph and introducing a new vertex \( w \) into the graph along with the edges \( \set{u,w} \) and \( \set{w,v} \).
Two graphs are said to be homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions.
A graph is called planar if it can be drawn in the plane without any edges crossing. Such a drawing is called a planar representation of the graph.
A planar graph splits the plane into regions bounded by edges on all sides and a region outside the graph that is unbounded.
If a graph is planar, then so is any graph obtained by elementary subdivision on that graph.
In the following figure, we show that \( K_4 \) is a planar graph by displaying an isomorphism such that no edge crosses another.
As another example, we show that \( Q_3 \) is a planar graph by displaying an isomorphism such that none of the edges cross each other.
Let \( G \) be a connected planar simple graph with \( e \) edges and \( v \) vertices. Let \( r \) be the number of regions in the planar representation of \( G \). Then, it is the case tha
$$ r = e - v + 2 $$
Two corollaries result from the Euler's formula for connected planar simple graphs
A graph is nonplanar if and only if it contains a subgraph homeomorphic to \( K_{3,3} \) or \( K_5 \).
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.
The chromatic number of a graph is the least number of colors needed for a coloring of that graph.
The four-color Theorem states that the chromatic number of a planar graph is no greater than four.
With a solid understanding of graphs, you are ready for exploring trees — a specialized form of graphs.
Help us create more engaging and effective content and keep it free of paywalls and advertisements!
Stay up to date with new material for free.