Unit 3: Graph theory
Mathematics-I notes · PTU syllabus (BSIT103/BSBC103)
On this page
Unit summary
Graphs model networks, routes, dependencies and social connections. This unit covers simple and multigraphs, directed and undirected graphs, Eulerian and Hamiltonian graphs, connectivity, traversals, graph optimisation, graph colouring, and trees and spanning trees.
After this unit you can
- Define types of graphs and basic terms
- Identify Eulerian and Hamiltonian graphs and test connectivity
- Traverse graphs and solve optimisation problems
- Colour graphs and find spanning trees
PTU syllabus topics
- Simple and multi-graphs
- directed and undirected graphs
- Eulerian and Hamiltonian graphs
- graph connectivity
- graph traversals
- graph optimization
- graph coloring
- trees and spanning trees
Visits every
Edge exactly once
Vertex exactly once
Circuit exists if
Connected and all degrees even
No simple rule (NP-complete)
Path exists if
Exactly 0 or 2 odd-degree vertices
Hard to test
Example
Königsberg bridges
Travelling salesman
Topic 1
Basic concepts and types of graphs
- Graph G = (V, E): a set of vertices and a set of edges joining pairs of vertices.
Simple graph
No loops or parallel edges
Multigraph
Parallel edges allowed
Pseudograph
Loops allowed
Directed graph
Edges have direction
Undirected graph
Edges have no direction
Weighted graph
Edges carry weights
Complete graph Kn
Every pair of vertices joined
Bipartite graph
Vertices split into two sets with edges only between sets
- Degree: number of edges at a vertex. Handshaking lemma: Σ deg(v) = 2|E|; the number of odd-degree vertices is even.
Topic 2
Eulerian and Hamiltonian graphs
Definition
Circuit using every edge exactly once
Cycle visiting every vertex exactly once
Test
Connected and every vertex has even degree (path if exactly two odd vertices)
No simple test; sufficient conditions such as Dirac's (deg ≥ n/2)
Origin
Königsberg bridges (Euler, 1736)
Hamilton's icosian game
Application
Route inspection, postal delivery
Travelling salesman
Topic 3
Graph connectivity
- Connected graph: a path exists between every pair of vertices; components are maximal connected subgraphs.
- Cut vertex and bridge: removal disconnects the graph; strongly connected digraph — directed path between every ordered pair.
Topic 4
Graph traversals
- Breadth-first search (BFS): visits neighbours level by level using a queue — shortest paths in unweighted graphs.
- Depth-first search (DFS): goes deep along a path before backtracking, using a stack or recursion — detecting cycles, connected components.
Topic 5
Graph optimisation
- Shortest path: Dijkstra's algorithm for non-negative weights.
- Minimum spanning tree: Kruskal's (add smallest edges without cycles) and Prim's (grow a tree from a vertex).
- Travelling salesman and route inspection (Chinese postman) problems.
Topic 6
Graph colouring
- Vertex colouring: assign colours so adjacent vertices differ; the minimum number is the chromatic number χ(G).
- Facts: χ(Kn) = n; bipartite graphs need 2 colours; planar graphs need at most 4 (four colour theorem).
- Applications: timetabling exams without clashes, register allocation in compilers, frequency assignment.
Topic 7
Trees and spanning trees
- Tree: connected graph with no cycles; with n vertices it has n − 1 edges; exactly one path between any two vertices.
- Rooted tree terms: root, parent, child, leaf, height; binary tree: each node has at most two children.
- Spanning tree: a subgraph that is a tree and includes all vertices; found by BFS or DFS; minimum spanning tree by Kruskal or Prim.
Example
Edges with weights A–B 1, B–C 3, A–C 2, C–D 4, B–D 5: Kruskal picks A–B (1), A–C (2), C–D (4) — total 7.
Key terms
- Degree
- Number of edges incident on a vertex
- Eulerian circuit
- Closed walk using every edge once
- Hamiltonian cycle
- Cycle visiting every vertex once
- Chromatic number
- Minimum colours for a proper colouring
- Spanning tree
- Tree containing all vertices of a graph
Quick revision
- Simple, multi, directed, undirected, weighted, complete, bipartite graphs; handshaking lemma.
- Euler's even-degree test; Hamiltonian cycles.
- Connectivity, components, cut vertices, bridges.
- BFS and DFS; Dijkstra; Kruskal and Prim.
- Colouring and chromatic number; trees (n − 1 edges), spanning trees.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.State the handshaking lemma.
- Q2.When does a graph have an Eulerian circuit?
- Q3.Distinguish BFS and DFS.
- Q4.What is the chromatic number of K4?
- Q5.How many edges does a tree with 10 vertices have?
- Q6.What is a minimum spanning tree?
Long-answer questions
- Q1.Explain types of graphs with examples.
- Q2.Explain Eulerian and Hamiltonian graphs.
- Q3.Explain graph traversal and graph optimisation algorithms.
- Q4.Explain graph colouring, trees and spanning trees.
Stuck on this unit?
Message SBS on WhatsApp for help with Mathematics-I, or to ask about studying B.Sc IT at Synetic.