chapter

Graph Fundamentals, Trees and Connectivity Short Notes for GATE CS

Graph Fundamentals, Trees and Connectivity short notes for GATE CS: 4 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice

graph fundamentals trees and connectivity short notes

Quick Revision: Enumeration Toolkit

Quick Revision Toolkit Concept Formula / Method Complete K_{n} τ (K_{n}) = n^{n - 2} General Graph τ (G) = det (L^{'}) Laplacian L L_{ii} = de g (i), L_{ij} = - 1 Tree Size Always n - 1 edges Jaccard Min 0 (for n \geq 4) Decision Checklist Is it K_{n} ? Use Cayley Sparse/Irregular? Use Laplacian Vertices labeled? Yes (default) Directed? Count parent choices

Quick Revision: Key Takeaways

Quick Revision: Key Takeaways 1 Definition: w (T) = \sum_{e \in T} w (e) . 2 Exchange Principle: Swapping edges e \in T_{2} ∖ T_{1} and f \in T_{1} ∖ T_{2} changes weight by w (e) - w (f) . 3 Core Theorem: If all w (T) share the same parity, all edges in any 2-edge-connected component must have the same parity . 4 Odd Component Rule: If a component has all odd edges, its vertex count V_{C} must be odd for w (T) to be even. 5 Bridges: Included in all trees; act as a constant parity shift. 6 Test Cases: Use an all-even graph (e.g., C_{4} with w = 2) and an all-odd graph (e.g., K_{3} with w = 1) to invalidate universal claims.

Final Cheat Sheet: Connectivity and Planarity

Quick Revision Cheat Sheet Connectivity Chain κ (G) \leq λ (G) \leq δ (G) Disconnected Max Edges E_{ma x} = \frac{( n - 1 ) ( n - 2 )}{2} Euler's Formula V - E + F = 2 Planarity Bounds General: E \leq 3 V - 6 Bipartite: E \leq 2 V - 4 Edge bounds are necessary but not sufficient for planarity.

1 more card in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Consider a connected simple graph with 10 vertices. If we partition its edges into a spanning tree and a set of extra edges, and the total number of edges is 15, how many edges are in the extra set?

Question 2

Level 1: Warm-up

Assertion (A): For a graph with 6 vertices, the reduced Laplacian matrix used in Kirchhoff's theorem is of size 5 \times 5 . Reason (R): The original Laplacian matrix is of size 6 \times 6, and the method requires deleting exactly one row and one column.

Question 3

Level 1: Warm-up

Consider the following: Assertion (A): A connected planar graph with 10 vertices and 15 edges has 7 faces. Reason (R): Euler's formula for connected planar graphs states V - E + F = 2 .

Question 4

Level 1: Warm-up

The number of spanning trees in a complete graph with 5 labeled vertices is

Question 5

Level 1: Warm-up

Which of the following statements about the row sums of the Laplacian matrix L of a simple undirected graph is true?

Question 6

Level 1: Warm-up

If the determinant of the reduced Laplacian matrix of a connected graph is 12, how many spanning trees does the graph have?

Question 7

Level 1: Warm-up

What is the maximum number of edges in a simple disconnected graph with 6 vertices?

Question 8

Level 1: Warm-up

Match the following connected planar graphs with their number of faces (including the outer face): \begin{array}{ll} \textbf{Graph} & \textbf{Vertices, Edges} \\ \text{I} & (4, 6) \\ \text{II} & (6, 9) \\ \text{III} & (8, 12) \end{array} \begin{array}{ll} \textbf{Faces} \\ \text{P} & 4 \\ \text{Q} & 5 \\ \text{R} & 6 \end{array}

Question 9

Level 1: Warm-up

Which of the following statements about the number of matchings m (n) in a path graph P_{n} is TRUE?

Question 10

Level 1: Warm-up

How many of the following triples (V, E, F) can represent a connected planar graph? (5, 8, 5), (6, 10, 6), (7, 12, 7), (8, 15, 8)

Free preview ends here

Login to view the complete short notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Graph Fundamentals, Trees and Connectivity Short Notes for GATE CS

Graph Fundamentals, Trees and Connectivity short notes for GATE CS: 4 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Quick Revision: Enumeration Toolkit

Quick Revision Toolkit

Concept	Formula / Method
Complete $K_{n}$	$τ (K_{n}) = n^{n - 2}$
General Graph	$τ (G) = det (L^{'})$
Laplacian $L$	$L_{ii} = de g (i)$ , $L_{ij} = - 1$
Tree Size	Always $n - 1$ edges
Jaccard Min	$0$ (for $n \geq 4$ )

Decision Checklist

Is it

K_{n}

?
Use Cayley

Sparse/Irregular?
Use Laplacian

Vertices labeled?
Yes (default)

Directed?
Count parent choices

Quick Revision: Key Takeaways

Definition:

w (T) = \sum_{e \in T} w (e)

Exchange Principle: Swapping edges

e \in T_{2} ∖ T_{1}

and

f \in T_{1} ∖ T_{2}

changes weight by

w (e) - w (f)

Core Theorem: If all

w (T)

share the same parity, all edges in any 2-edge-connected component must have the same parity.

Odd Component Rule: If a component has all odd edges, its vertex count

V_{C}

must be odd for

w (T)

to be even.

Bridges: Included in all trees; act as a constant parity shift.

Test Cases: Use an all-even graph (e.g.,

C_{4}

with

w = 2

) and an all-odd graph (e.g.,

K_{3}

with

w = 1

) to invalidate universal claims.

Final Cheat Sheet: Connectivity and Planarity

Quick Revision Cheat Sheet

Connectivity Chain

κ(G)≤λ(G)≤δ(G)

Disconnected Max Edges

Emax​=2(n−1)(n−2)​

Euler's Formula

V−E+F=2

Planarity Bounds

        General: E≤3V−6

        Bipartite: E≤2V−4

Edge bounds are necessary but not sufficient for planarity.

Exam Cheat Sheet — Matchings, Distances, Powers

Exam Cheat Sheet

Matchings

Matching = set of edges, no shared vertices. $\emptyset$ is valid.
Path $P_{n}$ matchings: $m (n) = m (n - 1) + m (n - 2)$ , $m (1) = 1$ , $m (2) = 2$ .
$m (n) = F_{n + 1}$ . For $P_{8}$ : $m (8) = 34$ .
Perfect $\Rightarrow$ Maximum $\Rightarrow$ Maximal (not reversible).

Distances

$d (u, v)$ = shortest path length (edges).
$ε (v) = max_{u} d (v, u)$ , $diam (G) = max_{v} ε (v)$ , $rad (G) = min_{v} ε (v)$ .
$rad (G) \leq diam (G) \leq 2 rad (G)$ .

Graph Powers

$G^{k}$ : edge iff $1 \leq d_{G} (u, v) \leq k$ .
$G^{2}$ from matrix: $N_{ij} = 1$ if $M_{ij} > 0$ or $(M^{2})_{ij} > 0$ , $i \neq = j$ .
$diam (G^{k}) = ⌈ diam (G) / k ⌉$ .
$G^{k} = K_{n}$ when $k \geq diam (G)$ .

If you see...

Question signal	Action
"number of matchings in $P_{n}$ "	Fibonacci table, include $\emptyset$
" $M^{2}$ " or " $N_{ij}$ from $M$ "	Graph square, threshold, zero diagonal
"diameter of $G^{2}$ "	$⌈ diam (G) /2 ⌉$
"maximal matching"	Greedy, not necessarily largest

Graph Fundamentals, Trees and Connectivity: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Engineering Mathematics MCQ

Consider a connected simple graph with 10 vertices. If we partition its edges into a spanning tree and a set of extra edges, and the total number of edges is 15, how many edges are in the extra set?

A.
6
B.
5
C.
4
D.
9

Correct Answer:

Step-by-Step Solution

Insight: A spanning tree of an $n$ -vertex graph always contains exactly $n - 1$ edges.

Exam route: The spanning tree has $10 - 1 = 9$ edges. The extra edges are the total minus the tree edges: $15 - 9 = 6$ .

Learning route:

Identify the total number of vertices $n = 10$ and total edges $E = 15$ .
Recall that any spanning tree of a graph with $n$ vertices must have exactly $n - 1$ edges.
Calculate the number of edges in the spanning tree: $10 - 1 = 9$ .
The extra edges are those not in the spanning tree. Subtract the tree edges from the total: $15 - 9 = 6$ .

Answer: 6

Question 2 · Engineering Mathematics MCQ

Assertion (A): For a graph with 6 vertices, the reduced Laplacian matrix used in Kirchhoff's theorem is of size $5 \times 5$ .

Reason (R): The original Laplacian matrix is of size $6 \times 6$ , and the method requires deleting exactly one row and one column.

A.
Both A and R are true and R is the correct explanation of A
B.
Both A and R are true but R is NOT the correct explanation of A
C.
A is true but R is false
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Insight: Kirchhoff's theorem requires reducing the $n \times n$ Laplacian to an $(n - 1) \times (n - 1)$ matrix by deleting one row and one column.

Exam route: For $n = 6$ , the original matrix is $6 \times 6$ . Deleting one row and one column yields a $5 \times 5$ matrix. R correctly explains why A is true.

Learning route:

Recall the statement of Kirchhoff's Matrix Tree Theorem.
The theorem states that the number of spanning trees is the determinant of any cofactor of the Laplacian matrix $L$ .
A cofactor is obtained by deleting exactly one row $i$ and one column $j$ (usually $i = j = 1$ ).
For a graph with $n = 6$ vertices, $L$ is a $6 \times 6$ matrix.
Deleting one row and one column reduces the dimensions by 1, resulting in a $5 \times 5$ matrix.
Thus, both A and R are true, and R is the direct mathematical reason for A.

Answer: Both A and R are true and R is the correct explanation of A

Question 3 · Engineering Mathematics MCQ

Consider the following:

Assertion (A): A connected planar graph with 10 vertices and 15 edges has 7 faces.

Reason (R): Euler's formula for connected planar graphs states $V - E + F = 2$ .

A.
Both A and R are true, and R is the correct explanation of A
B.
Both A and R are true, but R is NOT the correct explanation of A
C.
A is true but R is false
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Key idea: Use Euler's formula to verify the assertion.

Step 1: Euler's formula states $V - E + F = 2$ for connected planar graphs. So Reason (R) is true.

Step 2: Given $V = 10$ , $E = 15$ , substitute into Euler's formula: $10 - 15 + F = 2$ .

Step 3: Solve for $F$ : $F = 2 - 10 + 15 = 7$ .

Step 4: The assertion states $F = 7$ , which matches our calculation. So Assertion (A) is true.

Step 5: Reason (R) correctly explains why Assertion (A) is true.

Answer: Both A and R are true, and R is the correct explanation of A.

Question 4 · Engineering Mathematics MCQ

The number of spanning trees in a complete graph with 5 labeled vertices is

A.
125
B.
625
C.
24
D.
120

Correct Answer:

Step-by-Step Solution

Insight: Direct application of Cayley's formula for complete graphs.

Exam route: The formula for the number of spanning trees in $K_{n}$ is $n^{n - 2}$ . For $n = 5$ , this is $5^{5 - 2} = 5^{3} = 125$ .

Learning route:

Identify the graph as a complete graph $K_{n}$ with labeled vertices.
Recall Cayley's formula: $τ (K_{n}) = n^{n - 2}$ .
Substitute $n = 5$ into the formula: $5^{5 - 2} = 5^{3}$ .
Calculate $5^{3} = 125$ .

Answer: 125

Question 5 · Engineering Mathematics MCQ

Which of the following statements about the row sums of the Laplacian matrix $L$ of a simple undirected graph is true?

A.
The sum of elements in any row is always 0
B.
The sum of elements in any row is equal to the degree of the corresponding vertex
C.
The sum of elements in any row is always 1
D.
The sum of elements in any row is equal to the number of vertices

Correct Answer:

Step-by-Step Solution

Insight: The diagonal entry of the Laplacian is the vertex degree, and the off-diagonal entries are -1 for each adjacent vertex.

Exam route: Row sum = $de g (v_{i}) + \sum (- 1) = de g (v_{i}) - de g (v_{i}) = 0$ .

Learning route:

Recall the definition of the Laplacian matrix $L$ : $L_{ii} = de g (v_{i})$ and $L_{ij} = - 1$ if $(v_{i}, v_{j}) \in E$ , else $0$ .
The sum of the elements in row $i$ is the diagonal entry plus the sum of the off-diagonal entries.
There are exactly $de g (v_{i})$ off-diagonal entries equal to $- 1$ in row $i$ .
Sum = $de g (v_{i}) + (- de g (v_{i})) = 0$ .

Answer: The sum of elements in any row is always 0

Question 6 · Engineering Mathematics MCQ

If the determinant of the reduced Laplacian matrix of a connected graph is 12, how many spanning trees does the graph have?

A.
6
B.
12
C.
24
D.
144

Correct Answer:

Step-by-Step Solution

Key idea: Kirchhoff's Matrix Tree Theorem states that the number of spanning trees equals the determinant of any cofactor of the Laplacian matrix.

Step 1: According to Kirchhoff's theorem, $τ (G) = det (L^{'})$ , where $L^{'}$ is the reduced Laplacian matrix (obtained by deleting any one row and one column from the Laplacian).

Step 2: The problem states that $det (L^{'}) = 12$ .

Step 3: Therefore, the number of spanning trees is $τ (G) = 12$ .

Answer: 12.

Question 7 · Engineering Mathematics MCQ

What is the maximum number of edges in a simple disconnected graph with 6 vertices?

A.
10
B.
15
C.
12
D.
9

Correct Answer:

Step-by-Step Solution

Key idea: To maximize edges in a disconnected graph, make one component as large as possible ( $K_{n - 1}$ ) and one isolated vertex ( $K_{1}$ ).

Step 1: The formula is $E_{ma x} = \frac{( n - 1 ) ( n - 2 )}{2}$ .

Step 2: For $n = 6$ : $E_{ma x} = \frac{( 6 - 1 ) ( 6 - 2 )}{2} = \frac{5 \times 4}{2} = 10$ .

Answer: 10.

Question 8 · Engineering Mathematics MCQ

Match the following connected planar graphs with their number of faces (including the outer face):

\begin{array}{ll}

\textbf{Graph} & \textbf{Vertices, Edges} \\

\text{I} & (4, 6) \\

\text{II} & (6, 9) \\

\text{III} & (8, 12)

\end{array}

\begin{array}{ll}

\textbf{Faces} \\

\text{P} & 4 \\

\text{Q} & 5 \\

\text{R} & 6

\end{array}

A.
I-P, II-Q, III-R
B.
I-Q, II-R, III-P
C.
I-P, II-R, III-Q
D.
I-R, II-Q, III-P

Correct Answer:

Step-by-Step Solution

Key idea: This tests Euler's formula $V - E + F = 2$ for connected planar graphs.

Step 1: Apply Euler's formula to each graph:

Step 2: Graph I: $V = 4, E = 6$

$4 - 6 + F = 2 ⟹ F = 4$ → P

Step 3: Graph II: $V = 6, E = 9$

$6 - 9 + F = 2 ⟹ F = 5$ → Q

Step 4: Graph III: $V = 8, E = 12$

$8 - 12 + F = 2 ⟹ F = 6$ → R

Answer: I-P, II-Q, III-R

Question 9 · Engineering Mathematics MCQ

Which of the following statements about the number of matchings $m (n)$ in a path graph $P_{n}$ is TRUE?

A.
$m (n) = 2^{n}$
B.
$m (n) = F_{n + 1}$ , where $F_{k}$ is the $k$ -th Fibonacci number with $F_{1} = 1, F_{2} = 1$
C.
$m (n)$ does not include the empty matching
D.
$m (n) = F_{n}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a statement truth question on the explicit formula for matchings in a path, recognizable because it tests the exact relationship between $m (n)$ and the Fibonacci sequence.

Step 1: Recall the recurrence for $m (n)$ : $m (n) = m (n - 1) + m (n - 2)$ with base cases $m (1) = 1$ and $m (2) = 2$ .

Step 2: Compare this to the Fibonacci sequence $F_{k}$ where $F_{1} = 1, F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5, \dots$

Step 3: Check the values:

$m (1) = 1 = F_{2}$
$m (2) = 2 = F_{3}$
$m (3) = 3 = F_{4}$
$m (4) = 5 = F_{5}$

Step 4: The pattern is $m (n) = F_{n + 1}$ .

Answer: $m (n) = F_{n + 1}$

Question 10 · Engineering Mathematics MCQ

How many of the following triples $(V, E, F)$ can represent a connected planar graph?

$(5, 8, 5), (6, 10, 6), (7, 12, 7), (8, 15, 8)$

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: This tests validation using Euler's formula $V - E + F = 2$ for connected planar graphs.

Step 1: Check each triple against $V - E + F = 2$ :

Step 2: $(5, 8, 5)$ : $5 - 8 + 5 = 2$ ✓ Valid

Step 3: $(6, 10, 6)$ : $6 - 10 + 6 = 2$ ✓ Valid

Step 4: $(7, 12, 7)$ : $7 - 12 + 7 = 2$ ✓ Valid

Step 5: $(8, 15, 8)$ : $8 - 15 + 8 = 1 \neq = 2$ ✗ Invalid

Step 6: Count valid triples: 3

Answer: 3

graph fundamentals trees and connectivity short notes

Quick Revision: Enumeration Toolkit

Quick Revision Toolkit

Decision Checklist

Quick Revision: Key Takeaways

Quick Revision: Key Takeaways

Final Cheat Sheet: Connectivity and Planarity

Quick Revision Cheat Sheet

Try a question

Login to view the complete short notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Graph Fundamentals, Trees and Connectivity Short Notes for GATE CS

Quick Revision: Enumeration Toolkit

Quick Revision Toolkit

Decision Checklist

Quick Revision: Key Takeaways

Quick Revision: Key Takeaways

Final Cheat Sheet: Connectivity and Planarity

Quick Revision Cheat Sheet

Exam Cheat Sheet — Matchings, Distances, Powers

Exam Cheat Sheet

Graph Fundamentals, Trees and Connectivity: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More short notes in this unit