Discrete Math - Graph Terminologies

Table of Contents

In the previous lesson, you learned about graph models. In this article, you will learn about basic graph terminologies. There are some important terminologies that you will come across frequently, it is important to learn them first.

Definition 1:

Two vertices u and v are adjacent or neighbor in graph G if u and v are endpoints of edge e of G. Then we can say that edge e is incident with vertices u and v and also, connects u and v.

Definition 2:

The set of all neighbors of graph G = (V, E) is denoted by N(v) and it is called Neighborhood of v. The smaller v denotes a single vertex and larger V is a set of all vertices for the graph. If A is a subset of V, then N(A) is set of all vertices that are adjacent to at least one vertex in A.

$N(A) = \cup_{v \epsilon A}N(v)$

Definition 3:

The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop contributes twice to the degree of the vertex. The degree of a vertex is denoted by $deg(v)$ .

In the above figure, $deg(A) = deg(B) =2, deg(C) = 3$ . When the degree is 0 then the node is said to be isolated and when the degree is 1, the node is said to be a pendant.

For example, $deg(D) = 1$ and $deg(E) = 0$ .

The Handshake Theorem

The handshake theorem is a special theorem that takes the total amount of degrees of a graph. It goes like this, let $G = (V, E)$ be an undirected graph with m edges, then

$2m = \Sigma_{v \epsilon V} deg(v)$

Note: This applies even when multiple edges and loops are present.

Example:-

Consider the above example graph $G = (V, E)$ where $V = {A, B, C, D, E }$ and $E = { (A, B), (A, C), (B, C), (C, D) } = |E| = 4$

$2 x 4= deg(A) + deg(B) + deg(C) + deg(D) + deg(E)$

$8 = 2 + 2 + 3 + 1 + 0$

$8 = 8$

Right Hand Side = Left Hand Side

Theorem 2: Even Number of Vertices with Odd degree

An undirected graph has an even number of vertices of odd degree.

To prove the above statement, we will consider a graph $G = (V, E)$ where $V$ is the non-empty set of vertices and $E$ is a set of edges for the graph. Now, we will divide the $V$ into two sets – $V1$ and $V2$ .

The set $V1$ has all nodes with odd degrees. The set $V2$ has all the nodes with even degrees.

Therefore,

The Degree of Directed Edges

We already know that a directed graph has directed edges from the lesson – graph models.

In a graph with directed edges the in-degree of vertex v, denoted by deg-{v}, is the number of edges with v as a terminal vertex.

The out-degree of vertex v, denoted by deg+{v}, is the number of edges with v as an initial vertex for the edges.

Note:- A loop on the vertex contribute 1 to both in-degree and out-degree at the same time.

Example:-

Find the in-degree and out-degree for the following directed graph $G = (V, E)$ .

The Directed Graph with In-Degree and Out-Degrees for Each Node.

The solution to the problem of counting in-degree and out-degree of each node in the above-directed graph is given in tabular format. You can see that some nodes have 0 degrees or 0 out-degree.

In-Degree and Out-Degree for the Directed graph

Note that a graph with a directed edge and its underlying undirected graph has the same number of edges.