Questions
3–4 questions per semester paper
Difficulty
Medium
Importance
High yield for University Discrete Math exams
Overview
Graph Theory is the mathematical study of networks consisting of vertices and edges, serving as the foundation for data structures and network optimization. In university exams, mastering this topic is essential because it bridges discrete mathematics with practical computer science applications like shortest paths and resource allocation. Aspirants must focus on the structural properties of graphs, connectivity, and algorithmic constraints.
Graph Terminology
Graph theory terminology establishes the language used to describe networks, covering types of graphs and their connectivity properties. Understanding degree sequences, adjacency matrices, and path definitions is critical for solving descriptive and analytical exam problems.
- Handshaking Lemma: Sum of degrees equals twice the number of edges
- Simple Graph: No loops or multiple edges between vertices
- Complete Graph (Kn): Every pair of distinct vertices is connected by an edge
- Eulerian Path/Circuit: Traversal using every edge exactly once
- Hamiltonian Path/Cycle: Traversal visiting every vertex exactly once
Trees and Spanning Trees
A tree is a connected graph with no cycles, while a spanning tree is a subgraph that includes all vertices of the original graph without forming cycles. These concepts are frequently tested in the context of minimum spanning tree algorithms like Prim’s and Kruskal’s.
- A tree with n vertices has exactly n-1 edges
- Spanning trees connect all vertices with minimum cost
- Kruskal's Algorithm uses a greedy approach by sorting edges
- Prim's Algorithm grows the tree from a starting vertex
- Every connected graph has at least one spanning tree
Graph Coloring
Graph coloring is the process of assigning labels (colors) to elements of a graph subject to certain constraints, most commonly ensuring no two adjacent vertices share the same color. This subtopic is vital for scheduling problems and frequency assignment constraints.
- Chromatic Number chi(G): Minimum number of colors required to color the graph
- Four Color Theorem: Every planar graph can be colored with 4 colors
- Bipartite Graph: A graph with a chromatic number of 2
- Greedy coloring is an efficient but not always optimal strategy
- The problem of finding the chromatic number is NP-hard
Formula Sheet
Sum of degrees = 2 * E
Edges in a Tree = V - 1
Chromatic number of Complete Graph Kn = n
Exam Tip
Always draw a small sample graph to test your logic when applying theorems like the Handshaking Lemma to ensure your edge-to-vertex count remains consistent.
Common Mistakes
- Confusing the definition of Eulerian paths with Hamiltonian paths during exam stress
- Failing to verify if a graph is planar before applying coloring theorems
- Ignoring the directionality in Directed Acyclic Graphs (DAGs) when calculating degrees
More Revision Notes
Ready to test yourself?
Play topic-wise Graph Theory questions in Aspirant Arcade — gamified MCQ practice.
Download Free