Introduction to Graphs: Loops, Parallel Edges and Adjacent Vertices with Worked Examples

A graph picture can hide three counting traps. A loop counts differently in degree, parallel edges remain separate edge objects, and adjacency is not incidence. Fixed names for the vertices and edges make every count auditable. The Graph Theory for GATE CS connects these foundations to later graph topics, while GATE Guidance by Sanchit Sir provides a structured course path.

Graphs begin with vertex and edge sets

An undirected graph is G = (V, E), where V is the vertex set and E is the edge collection. Its order is |V|, and its size is |E|. With parallel edges, E must retain multiplicity instead of collapsing repeated endpoint pairs.

Use this graph throughout:

V = {A, B, C, D, E}

E = {l, e1, e2, e3, e4, e5}, where:

• l = (A,A)

• e1 = {A,B} and e2 = {A,B}

• e3 = {A,C}

• e4 = {B,C}

• e5 = {C,D}

Therefore, |V| = 5 and |E| = 6. Although e1 and e2 share endpoints, they are two edge objects. Treat E as an edge multiset, with l and e1 to e5 fixed as labelled above.

Graph incidence, adjacency and neighbourhood

Edge e3 has endpoints A and C, so it is incident on both. Loop l has both ends at A. Incidence connects an edge with an endpoint; vertex adjacency describes vertices joined by an edge.

The distinct-vertex adjacency pairs are A-B, A-C, B-C and C-D. Two A-B edges give one neighbour relationship but two incidences at each endpoint. Let N* exclude the vertex itself:

• N*(A) = {B,C}

• N*(B) = {A,C}

• N*(C) = {A,B,D}

• N*(D) = {C}

• N*(E) = empty set

Some textbooks make a looped vertex self-adjacent. Under that convention, A is adjacent to itself. Our N* excludes that relationship, so check the convention in each question.

Edges are adjacent when they share an endpoint. Thus e1 and e2 are parallel and adjacent, e3 and e4 are adjacent but not parallel, and e1 and e5 are neither.

Loops, parallel edges and graph classes

A loop has the same vertex at both endpoints, so l = (A,A) is one. Parallel edges are distinct edges with the same endpoint pair, making e1 and e2 parallel.

A simple undirected graph has neither loops nor parallel edges. This graph is not simple: l is a loop, and {e1,e2} is a parallel pair. Multigraph and pseudograph vary across books, so use the question's definition. Here, a multigraph may have parallel edges but no loops, while a pseudograph may have both.

The picture also contains a pendant vertex D, whose degree is 1, and an isolated vertex E, whose degree is 0. It has two connected components: {A,B,C,D} and {E}.

Worked graph example: edges, degrees and neighbours

Read each degree from the edge list. A loop contributes 2 because both its ends meet the same vertex.

For A, deg(A) = 2 + 1 + 1 + 1 = 5, from l, e1, e2 and e3. Similarly, deg(B) = 1 + 1 + 1 = 3, deg(C) = 1 + 1 + 1 = 3, deg(D) = 1, and deg(E) = 0.

At A, the degree is 5, but there are only 2 distinct other-vertex neighbours. The loop and repeated A-B edge break the shortcut that degree equals neighbour count.

Graph degree sum as an error check

Add the degrees:

5 + 3 + 3 + 1 + 0 = 12

The handshaking identity gives 2|E| = 2 x 6 = 12. It still works when a loop supplies two degree contributions and each parallel edge is counted separately.

Two wrong totals reveal common errors. Counting l once in deg(A) produces 11. Merging e1 and e2 gives the wrong size 5 and removes one degree contribution from both A and B, changing the sum from 12 to 10 because two edges became one.

A loop is one edge for |E|, but it contributes two to the degree of its vertex.

Underlying simple graph: remove loops and duplicate edges

For the underlying simple graph, delete l, then replace {e1,e2} with one edge AB. The vertex set remains {A,B,C,D,E}, and the edge set is {AB, AC, BC, CD}. Its order is 5 and size 4.

The new degrees are deg(A)=2, deg(B)=2, deg(C)=3, deg(D)=1 and deg(E)=0. A second audit gives 2 + 2 + 3 + 1 + 0 = 8 = 2 x 4.

The four distinct-vertex adjacency pairs and isolated E survive. The A-B multiplicity disappears, as does self-adjacency at A under the loop convention.

Graph terminology traps hidden in wording

Test each phrase against the edge list:

1. How many edge objects are incident on A, counting the loop as one edge object? Four: l, e1, e2 and e3. Its degree is still 5 because l contributes twice there.

2. How many distinct other vertices are adjacent to A? Two: B and C.

3. Is G simple? No. The loop l and parallel pair {e1,e2} are independent witnesses.

Now delete l and only e2 from G. Edges e1, e3, e4 and e5 remain, so the size is 4. The degrees are A=2, B=2, C=3, D=1, E=0, and their sum 8 equals 2 x 4. The order stays 5 because no vertex was deleted.

Apply these distinctions in the Graph Theory MCQs, which gives solved practice across Euler paths, colouring and trees.

Graph basics: the short version and next step

• A graph is G = (V, E).

• A loop has the same endpoint twice.

• Parallel edges are distinct edges with the same endpoint pair.

• Vertex adjacency, edge incidence and degree answer different questions.

• A loop adds 1 to size but 2 to degree.

For a 60-second self-check, recover |V|=5, |E|=6, deg(A)=5, N*(A)={B,C}, and both components from the original edge list. If one value is missed, redraw the figure and label every edge object.

Use the GATE CS category for the wider preparation path. Continue structured concept learning through GATE Guidance, then use the GATE Test Series for timed practice after concept study and topic-wise questions. Keep the edge objects visible, and these definitions become bookkeeping rather than guesswork.