Graph Terminologies

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.

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 .

In the above figure, . 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, and .

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 be an undirected graph with m edges, then

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

Example:-

Consider the above example  graph where and

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 where is the non-empty set of vertices and is a set of edges for the graph. Now, we will divide the into two sets – and .

The set has all nodes with odd degrees. The set has all the nodes with even degrees.

Therefore,

Example:-

To prove this theorem let’s take a graph with .

The above graph we can split the vertices into V1 (odd degrees) and V2 (even degrees).

Now, we need the total number of edges in G which is .

therefore,

R.H.S = L.H.S

That means, the theorem is correct and also, is a set with even number of vertices with odd degrees.

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 .

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.

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