Graphs: Definition and terminology

Graph G consists of two things:

1. A set V=V(G) whose elements are called vertices, points or nodes of G.

2. A set E = E(G) of an unordered pair of distinct vertices called edges of G.

3. We denote such a graph by G(V, E) vertices u and v are said to be adjacent if there is an edge e ={u, v}.

4. In such a case u and v are called the endpoint of e={u, v} and e are said to connect u and v.

Degree of a Vertex:

The degree of a vertex is the number of edges incident on a vertex v. The self-loop is counted twice. The degree of a vertex is denoted by d(v).

Example1: Consider the graph G shown in fig. Determine the degree of each vertex.

Solution: The degree of each vertex is as follows:

                  d(a)=3;       d(b)=5;       d(c) = 2;       d(d)=2.

Example2: Verify that the sum of the degrees of all the vertices is even for the graph shown in fig:

Solution: The sum of the degrees of all the vertices is:

                  =d (v₁)+d(v₂ )+d(v₃ )+d(v₄ )+d(v₅ )+d(v₆ )+d(v₇ )+d(v₈)
                  = 2+3+3+3+3+4+2+2=22, which is even.

Example3: Verify that there are even numbers of vertices of odd degrees in the graph shown in fig:

Solution: The number of vertices of degree odd is 8, and each has a degree three in the above graph. Hence, we have even number of vertices of odd degrees.

Path:

A path of length n is a sequence of n+1 vertices of a graph in which each pair of vertices is an edge of the graph.

1. A Simple Path: The path is called simple one if no edge is repeated in the path, i.e., all the vertices are distinct except that first vertex equal to the last vertex.
2. An Elementary Path: The path is called elementary one if no vertex is repeated in the path, i.e., all the vertices are distinct.
3. Circuit or Closed Path: The circuit or closed path is a path in which starts and ends at the same vertex, i.e., v₀=v_n.
4. Simple Circuit Path: The simple circuit is a simple path which is a circuit.

Example: Consider the graph shown in fig: Give an example of the following:

1. A simple path fromV₁ to V₆.
2. An elementary path from V₁ to V₆.
3. A simple path which is not elementary from V₁ to V₆.
4. A path which is not simple and starting fromV₂.
5. A simple circuit starting from V₁
6. A circuit which is not simple and starting from V₂.

Solution:

1. A simple path fromV₁ to V₆.
           V_1,V_2,V_3,V_4,V_5,V₆.
2. An elementary path from V₁ to V₆.
           V_1,V_2,V_3,V_5,V_4,V₆.
3. A simple path which is not elementary from V₁ to V₆.
           V_1,V_2,V_3,V_5,V_2,V_4,V₆.
4. A path which is not simple and starting fromV₂.
           V_2,V_3,V_4,V_5,V_3,V_4,V₆.
5. A simple circuit starting fromV₁.
           V_1,V_2,V_4,V_6,V_5,V_3,V₁
6. A circuit which is not simple and starting from V₂.
           V_2,V_3,V_1,V_2,V_5,V_4,V₂.

Pendant Vertex: A vertex with degree one is called a Pendant Vertex.

Pendant Edge: The only edge which is an incident with a pendant vertex is called the Pendant Edge.

Odd Vertex: A vertex having degree odd is called an odd vertex.

Even Vertex: A vertex having a degree even is called an even vertex.

Incident Edge: An edge is called incident with the vertices is connects.

Adjacent Vertices: Two vertices are called adjacent if an edge links them. If there is an edge (u, v), then we can say vertex u is adjacent to vertex v, and vertex v is adjacent to vertex u.

Example: Consider the graph as shown in fig:

Determine the following:

1. Pendant Vertices
2. Pendant Edges
3. Odd vertices
4. Even Vertices
5. Incident Edges
6. Adjacent Vertices

Solution:

1. The vertex V₅is the pendant vertex.
2. The edge (V_4,V₅) or e₅ is the pendant edge.
3. The vertices V₃ and V₅ are odd vertices.
4. The vertices V_1, V_2,and V₄ are even vertices.
5. The edge e₁ is an incident on V_1, and V₂.
       The edge e₂ is an incident on V₁ and V₃.
       The edge e₃ is an incident on V₂ and V₃.
       The edge e₄ is an incident on V₃ and V₄.
       The edge e₅ is an incident on V₄ and V₅.
6. The vertex V₁ is adjacent to V₂ and V₃.
       The vertex V₂ is adjacent to V₁ and V₂.
       The vertex V₃ is adjacent to V₁ and V₄
       The vertex V₄ is adjacent to V₃ and V₅
       The vertex V₅ is adjacent to V₄.

Self-Loop: A self-loop is an edge e if it has the same endpoint.

The graph shown in fig contains the self-loop at vertex b,i.e., e=(b, b).

Isolated Vertex: A vertex with degree 0 is called Isolated Vertex.

Cut Set: Consider a graph G=(V, E).A cut set for G is the smallest set of edges such that the removal of the set, disconnected the graph whereas the removal of any proper subset of this set left a connected subgraph.

Example: Consider the graph shown in fig. Determine the cut set for this group.

Solution: For this graph, the edge set {(V_1,V₅),(V_7,V₅)} is a cut set. After the removal of the set, we have left with a disconnected subgraph. While after the removal of any of its proper subset, we have left with a connected subgraph.

Cut Points or Cut Vertices: Consider a graph G=(V, E). A cut point for a graph G is a vertex v such that G-v has more connected components than G or disconnected.

The subgraph G-v is obtained by deleting the vertex v from graph G and also deleting the entire edges incident on v.

Example: Consider the graph shown in fig. Determine the subgraphs

(i)G-v₁     (ii) G-v₃     (iii) G-v₅

Solution:

1. The subgraph G-v₁ is shown in fig
2. The subgraph G-v₃ is shown in fig
3. The subgraph G-v₅ is shown in fig

Bridge (Cut Edges): Consider a graph G=(V, E).A bridge for a graph G, is an edge e such that G-e has more connected components than G or disconnected.

Example: Consider the graph shown in fig. Determine the subgraphs

(i)G-e₁     (ii) G-e₃     (iii) G-e₄

Solution:

1. The subgraph G-e₁ is shown in fig
2. The subgraph G-e₃ is shown in fig
3. The subgraph G-e₄ is shown in fig