Degree of a Vertex: Isolated and Pendant Vertices, the Handshaking Lemma, and a Worked Degree Sequence
Learn how to count vertex degree correctly, including loops, then test degree sequences with a seven-vertex example and the handshaking lemma.
KnowledgeGate Team
Exam prep & CS education

A graph picture can make degree look like a quick line-counting exercise. But a loop, an isolated vertex, an unsorted list, or one missing value can turn that shortcut into a wrong answer. The incidence rule, a seven-vertex example, the handshaking lemma, and parity consequences provide tools for testing degree sequences.
Degree of a Vertex Counts Edge Incidences
For an undirected graph G=(V,E), the degree deg(v) is the number of edge ends incident on vertex v. In a simple graph with n vertices, 0 <= deg(v) <= n-1. Here, neighbour count and incidence count agree. With parallel edges they need not, because each edge counts separately. A loop contributes two to the degree because both its ends meet the same vertex.
Consider the pseudograph V={P,Q,R} and E={PQ,QR,QQ}, where QQ is a loop. Vertex P has one incidence, Q has one from PQ, one from QR, and two from QQ, while R has one. Therefore:
deg(P)=1, deg(Q)=4, deg(R)=1
The check is 1+4+1=6=2|E|, since |E|=3. This is a pseudograph, not a simple graph, because it contains the loop QQ.
You can place this concept inside the GATE CS Exam Preparation route. For loops, parallel edges, adjacency and incidence conventions, use Introduction to Graphs: Loops, Parallel Edges and Adjacent Vertices with Worked Examples. That foundation separates edge objects from neighbour relationships; incidence counting then leads to isolated and pendant vertices, handshaking and the degree sequence below.
Isolated and Pendant Vertices Are Degree-Zero and Degree-One Cases
An isolated vertex has deg(v)=0. It has no incident edge and forms a one-vertex connected component. A pendant vertex, also called a leaf, has deg(v)=1. It belongs to a non-trivial component through its single incident edge.
Use the fixed graph V={A,B,C,D,E,F,G} with E={AB,AC,AD,BC,BD,CE,DE,EF}. Vertex G occurs in no edge, so it is isolated. The only edge incident on F is EF, so F is pendant. Removing EF isolates F and increases the number of connected components. However, a bridge need not be incident on a pendant vertex.
At the boundaries, a one-vertex graph with no edges has one isolated vertex. In the two-vertex graph containing only edge UV, both U and V have degree one, so both are pendant.
Worked Graph: Build the Degree Table and Degree Sequence
Count from an incidence ledger before trying to read degrees from a drawing. For the same simple undirected graph, the ledger is:
Vertex | Incident edges |
|---|---|
A |
|
B |
|
C |
|
D |
|
E |
|
F |
|
G | none |
Thus deg(A)=3, deg(B)=3, deg(C)=3, deg(D)=3, deg(E)=3, deg(F)=1, and deg(G)=0. The labelled degree list in A-to-G order is (3,3,3,3,3,1,0). It is already in non-increasing order, so the degree sequence is also (3,3,3,3,3,1,0).
Now check the construction. It has |V|=7 and |E|=8. Its degree sum is
3+3+3+3+3+1+0=16=2*8.
The odd-degree vertices are A, B, C, D, E and F. There are six of them, which is an even count. Since the listed edges explicitly construct a graph with these degrees, the displayed sequence is graphical.

Handshaking Lemma: Why the Degree Sum Is Twice the Edge Count
For every finite undirected graph, the handshaking lemma states:
sum(deg(v), v in V)=2|E|.
This follows by double-counting vertex-edge incidences. Every non-loop edge has two endpoints and contributes one incidence at each endpoint. A loop contributes two incidences at its single endpoint. Therefore every edge contributes exactly two to the total degree sum.
In the fixed graph, sum deg(v)=16 and 2|E|=2*8=16. In the loop example, 1+4+1=6=2*3. The lemma is an identity for finite undirected graphs, not a pattern that merely happens to fit these drawings.
For a directed graph, sum indeg(v)=sum outdeg(v)=|E|, so the sum of all total degrees is 2|E|.

Handshaking Consequences: Missing Degrees and Odd-Vertex Parity
Because 2|E| is even, every undirected graph has an even degree sum. Split that sum into even-degree and odd-degree terms. The even terms do not affect parity, and an even total can contain only an even number of odd terms. Therefore every undirected graph has an even number of odd-degree vertices. Our fixed graph has six: A, B, C, D, E and F.
Now suppose a simple graph has six vertices, nine edges, and degree list (4,4,3,3,2,x). The handshaking lemma gives:
4+4+3+3+2+x=2*9
16+x=18
x=2
The completed list (4,4,3,3,2,2) has two odd entries, so the parity check agrees.
By contrast, (4,3,3,2,1) has sum 4+3+3+2+1=13. An odd sum cannot equal 2|E|, so no undirected graph has this degree sequence. An even sum is necessary, but it is not sufficient for a sequence to be graphical.
Degree Sequences: Necessary Checks Versus an Actual Construction
A degree sequence lists vertex degrees in non-increasing order. For a proposed simple-graph sequence of length n, begin with three checks:
Every entry is an integer in
[0,n-1].The sum is even.
Structural claims are compatible. For example, a universal vertex must be adjacent to every isolated-looking candidate, which creates a contradiction if that candidate is assigned degree zero.
The sequence (3,3,3,3,3,1,0) is graphical because our edge set constructs it. Now consider (3,3,3,1). Its entries are in range for four vertices, and its sum is the even number 10. Yet each degree-3 vertex in a four-vertex simple graph must meet all three other vertices. The fourth vertex must therefore meet those three degree-3 vertices, giving it degree 3, not degree 1. The sequence is not graphical.
The handshaking lemma and local bounds can disprove many candidates, but passing them does not build a graph. A direct edge construction proves one sequence graphical. For candidates without an obvious construction, Degree Sequences and Graph Isomorphism for GATE: Handshake Lemma and Havel-Hakimi Drills develops full Havel-Hakimi reductions and then uses degree sequences as isomorphism filters.
Degree-of-Vertex Exam Questions and Traps
Typical tasks ask you to read degrees from a drawing, count a loop as two incidences, identify isolated and pendant vertices, find a missing degree using 2|E|, use odd-degree parity to reject data, or decide whether a sequence is merely plausible or actually graphical.
Mistake | Failure on the worked values | Repair |
|---|---|---|
Count loop | Gets | Count both ends of the loop |
Delete zero from | Loses vertex G | Keep one degree entry per vertex |
Call F isolated | Ignores | Classify F as pendant |
Accept | Misses its odd sum, 13 | Reject any odd degree sum |
Accept | Treats a necessary test as sufficient | Check a construction or use a graphicality test |
First derive incidence, parity and graphicality checks from the worked graph. Then use Degree of Vertex MCQs: 12 Solved Questions on Isolated and Pendant Vertices, Handshaking Lemma, and Degree Sequences for 12 option-by-option drills that apply the same invariants to maximum degree, parity, isolated vertices and graphicality.
Degree of a Vertex: The Short Version and Next Step
Degree counts incidences.
A loop counts twice.
Degree zero means isolated.
Degree one means pendant.
The degree sum is
2|E|, so the number of odd-degree vertices is even.
For the worked graph, (3,3,3,3,3,1,0) -> 16 = 2*8. Redraw its eight edges from the edge list, reconstruct every degree, then solve the six-vertex missing-degree example without looking. Continue through Discrete Mathematics and Graph Theory with GATE Guidance by Sanchit Sir.
Keep learning
Degree of Vertex MCQs: 12 Solved Questions on Isolated and Pendant Vertices, Handshaking Lemma, and Degree Sequences
Solve 12 vertex-degree MCQs with fresh explanations covering maximum degree, isolated and pendant vertices, regular graphs, parity, and graphical sequences.
Degree Sequences and Graph Isomorphism for GATE: Handshake Lemma and Havel-Hakimi Drills
Use the Handshake Lemma and Havel-Hakimi mechanically, then learn why matching degree sequences cannot by themselves prove graph isomorphism.
Introduction to Graphs: Loops, Parallel Edges and Adjacent Vertices with Worked Examples
Build every basic graph term from one five-vertex example. Track a loop and parallel edges correctly, audit the degree sum, then simplify the graph.
Interface Addressing Explained: Memory-Mapped vs Isolated I/O with Worked Examples
Understand what an interface address selects, how memory-mapped and isolated I/O differ, and why partial decoding creates multiple addresses for the same register.





