ACompressed recap
🧾
A graph has vertices and edges (directed or not, possibly weighted). Σ deg = 2e, so odd-degree vertices come in pairs; in a directed graph Σ in = Σ out = e. Paths repeat no vertex, cycles close a path. Connected graphs need ≥ n − 1 edges; k components need ≥ n − k. Max edges: n(n − 1)/2 (undirected), n(n − 1) (directed); with k components (n − k)(n − k + 1)/2. Trees are connected and acyclic; DAGs have no directed cycle.
BMerged rule card
6.1 Graph vocabulary
- 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.
CInterleaved GATE-style questions
Q1NAT1 markEdges
A graph has degree sequence 4, 4, 3, 3, 2, 2. How many edges?
Numerical answer: ________
Q2NAT2 marksDisconnected
What is the maximum number of edges in a disconnected simple graph with 8 vertices?
Numerical answer: ________
Q3MCQ1 markDirected
Maximum edges in a simple directed graph with 6 vertices (no self-loops):
- (A) 36
- (B) 12
- (C) 15
- (D) 30
Q4NAT1 markForest
A forest has 20 vertices and 4 trees. How many edges?
Numerical answer: ________
Q5MCQ2 marksDegree sequence
Which degree sequence is possible for a simple graph?
- (A) 2, 2, 2, 2
- (B) 3, 2, 1
- (C) 3, 3, 3, 1
- (D) 4, 1, 1, 1
Q6MSQ2 marksFacts
Which are true?
- (A) A connected graph with n vertices and n edges has no cycle.
- (B) A cycle in a simple undirected graph has at least 3 vertices.
- (C) Every tree is a forest.
- (D) Every DAG has at least one vertex of in-degree 0.
Q7NAT2 marksComponents
A simple graph has 15 vertices and 4 connected components. At least how many edges?
Numerical answer: ________
Q8MCQ1 markSum
In a directed graph with 10 edges, the sum of all in-degrees is:
- (A) 20
- (B) 5
- (C) 10
- (D) depends on the graph
DAnswer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 91 mark
18 / 2 = 9.
Re-read: Lesson 6.1 — Graph vocabulary
Q2 Answer: 212 marks
K₇ plus an isolated vertex: 7·6/2 = 21.
Re-read: Lesson 6.1 — Graph vocabulary
Q3 Answer: (D)1 mark
6 · 5.
- (A) is wrong: That allows self-loops.
- (B) is wrong: Too small.
- (C) is wrong: That is undirected.
Re-read: Lesson 6.1 — Graph vocabulary
Q4 Answer: 161 mark
n − k = 16.
Re-read: Lesson 6.1 — Graph vocabulary
Q5 Answer: (A)2 marks
A 4-cycle.
- (B) is wrong: The sum 6 is even, but 3 vertices allow a maximum degree of 2.
- (C) is wrong: The three degree-3 vertices force the last to degree 3.
- (D) is wrong: Degree 4 needs at least 5 vertices.
Re-read: Lesson 6.1 — Graph vocabulary
Q6 Answer: (B) (C) (D)2 marks
n edges on a connected n-vertex graph give exactly one cycle.
- (A) is wrong: One more than a tree: exactly one cycle.
Re-read: Lesson 6.1 — Graph vocabulary
Q7 Answer: 112 marks
n − k = 11.
Re-read: Lesson 6.1 — Graph vocabulary
Q8 Answer: (C)1 mark
Each edge ends at exactly one vertex.
- (A) is wrong: That is the undirected degree sum.
- (B) is wrong: Too small.
- (D) is wrong: It is always e.
Re-read: Lesson 6.1 — Graph vocabulary