Graph vocabulary

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How many distinct max-heaps can be built from 5 distinct keys? from Lesson 5.4
• After deleting the root of a heap, which element moves to the root first? from Lesson 5.2
• A tree has n nodes. How many edges? from Lesson 4.1

1 · The Hook

🎣

A metro map has stations and the lines between them; a social network has people and friendships; a course catalogue has subjects and “must be taken before” arrows. None of these has a single top or a unique parent, and you can go round in circles. The structure that models all of them is a graph.

2 · Predict First

🤔

Five friends each shake hands with every other friend exactly once. How many handshakes happen? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Each of 5 people shakes 4 hands: 5 × 4 = 20 hand-uses, but each handshake uses two hands: 10 = 5·4/2.

Graph, vertex, edge

A graph G = (V, E) is a set V of vertices and a set E of edges, each edge joining two vertices. With n = |V| and e = |E|:

• Undirected graph: edge {u, v} has no direction; u and v are adjacent (neighbours). Directed graph: edge (u, v) goes from u to v.
• Weighted graph: each edge carries a number (cost, length).
• Simple graph: no self-loops (edge from a vertex to itself) and no parallel edges. GATE assumes simple graphs unless told otherwise.

Degree and the handshake lemma

The degree of a vertex is the number of edges touching it. Every edge adds 1 to two degrees, so the handshake lemma holds: Σ deg(v) = 2e. Consequence: the number of odd-degree vertices is even. In a directed graph, each vertex has an in-degree and an out-degree, and Σ in-degree = Σ out-degree = e.

Walks, paths, cycles, connectivity

• A walk is a sequence of vertices joined by edges; a path repeats no vertex; a cycle is a closed path (length ≥ 3 in a simple undirected graph).
• An undirected graph is connected if every pair of vertices is joined by a path. The maximal connected pieces are its connected components. (A directed graph is strongly connected if every vertex can reach every other along the arrows.)
• A tree (Lesson 4.1) is a connected graph with no cycle; it has n − 1 edges. A forest is a graph with no cycle: with k trees it has n − k edges.
• A DAG is a directed acyclic graph: arrows but no directed cycle (e.g. prerequisites).
• The complete graph Kₙ has every pair adjacent: n(n − 1)/2 edges. A graph is dense if e is close to n², sparse if e is close to n.

Counting facts

4 · Visual

Running example: 8 vertices, 8 edges, two connected components.

A directed graph: 2 → 4 → 5 → 2 is a directed cycle, so it is not a DAG.

Undirected example (degrees in brackets):

   1(3) ----- 3(2)
   /  \          \
0(2)   \          5(2)        6(1) ----- 7(1)
   \    \        /
   2(2) ----- 4(3)

sum of degrees = 2+3+2+2+3+2+1+1 = 16 = 2 x 8 edges
components: {0,1,2,3,4,5} and {6,7}
cycle: 0-1-4-2-0   path: 0-1-3-5

The handshake lemma checks any degree list: the sum must be twice the edge count.

5 · Worked Examples

Example 1 Easy

In the directed graph above, give the in-degree and out-degree of each vertex and check Σ in = Σ out = e.

Solution

Out: 1:2, 2:1, 3:1, 4:1, 5:1. In: 1:0, 2:2, 3:1, 4:2, 5:1. Both sums are 6 = e.

Example 2 Medium

Can a simple graph on 4 vertices have degrees 3, 3, 3, 1?

Solution

No. The sum is 10 (even, so the handshake lemma alone does not rule it out), but three vertices of degree 3 must each be adjacent to all three others, which forces the fourth vertex to have degree 3, not 1.

Example 3 GATE

What is the maximum number of edges in a simple undirected graph with 10 vertices and 3 connected components?

Solution

Put all edges in one component: one K₈ plus two isolated vertices: 8·7/2 = 28 = (n − k)(n − k + 1)/2 with n = 10, k = 3.

6 · GATE Traps

⚠️

• Handshake: Σ deg = 2e, not e.
• An even degree sum does not guarantee that a simple graph with those degrees exists.
• Directed maximum is n(n − 1); undirected is n(n − 1)/2.
• A connected graph needs at least n − 1 edges, but n − 1 edges do not guarantee connectivity.
• A path repeats no vertex; a walk may.

8 · Memory Hook

🧠

“Every handshake has two hands.” Σ deg = 2e; odd-degree vertices come in pairs.

9 · Connect the Dots

Lesson 6.1 gave the words; a program needs the graph in memory. Next lesson answers: what are the ways to store a graph in C, and which one makes each operation fast?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markHandshake

A simple undirected graph has 12 vertices, each of degree 4. How many edges?

Numerical answer: ________

Q2NAT1 markMaximum

Maximum edges in a simple undirected graph with 9 vertices?

Numerical answer: ________

Q3MCQ2 marksOdd degrees

A graph has 7 vertices with degrees 1, 2, 2, 3, 3, 3 and x. Which value of x is ruled out by the handshake lemma?

• (A) 2
• (B) 1
• (C) 6
• (D) 4

Q4MSQ1 markFacts

Which are true for every simple undirected graph?

• (A) The number of odd-degree vertices is even.
• (B) A graph with n − 1 edges is connected.
• (C) A forest with n vertices and k trees has n − k edges.
• (D) A connected graph on n vertices has at least n − 1 edges.

Q5NAT2 marksCounting

How many simple undirected graphs are there on 4 labelled vertices?

Numerical answer: ________

11 · Rule Card

• G = (V, E); undirected / directed; weighted; simple = no loops, no parallel edges.
• Σ deg = 2e; odd-degree vertices even in number; directed: Σ in = Σ out = e.
• Max edges: n(n − 1)/2 undirected, n(n − 1) directed; graphs on n labelled vertices: 2^(n(n−1)/2).
• Connected ⇒ e ≥ n − 1; k components ⇒ e ≥ n − k; max with k components (n − k)(n − k + 1)/2.
• Tree: connected, acyclic, n − 1 edges; forest: n − k edges; DAG: no directed cycle.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

graph, vertex, edgedirected / undirected / weighted / simpledegree, in/out-degreehandshake lemmawalk, path, cycleconnected componentcomplete graph, forest, DAG

13 · Answer Vault