Unit 4: Graph theory
Discrete Structures & Optimization notes · PTU syllabus (PGCA1917)
On this page
Unit summary
Graphs model networks, schedules and maps. This unit covers directed and undirected graphs, Eulerian and Hamiltonian chains and cycles, trees, chromatic number, connectivity, graph colouring, planar and connected graphs, and isomorphism and homomorphism with applications.
After this unit you can
- Classify graphs and use their basic properties
- Identify Eulerian and Hamiltonian paths and cycles
- Work with trees, connectivity and planar graphs
- Colour graphs and test isomorphism
PTU syllabus topics
- Directed and undirected graphs
- Eulerian and Hamiltonian chains and cycles
- trees
- chromatic number
- connectivity
- graph coloring
- plane and connected graphs
- isomorphism and homomorphism and their applications
Topic 1
Directed and undirected 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.
- Handshaking lemma: the sum of the degrees of all vertices is twice the number of edges, so the number of odd-degree vertices is even. In a digraph, the sum of in-degrees equals the sum of out-degrees equals the number of edges.
Example
Degrees in a digraph: in a directed graph with edges A→B, A→C and B→C, A has out-degree 2 and in-degree 0; C has in-degree 2. The sum of in-degrees = sum of out-degrees = 3 = number of edges.
Exam tip
Handshaking lemma (undirected): Σ degrees = 2|E|.
Topic 2
Eulerian and Hamiltonian chains and cycles
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
Example
Testing for Euler paths: a connected graph with degrees 2, 3, 3 and 2 has exactly two odd-degree vertices, so it has an Euler path (starting at one odd vertex and ending at the other) but no Euler circuit.
Exam tip
Euler circuit: all degrees even. Euler path: exactly two odd-degree vertices.
Topic 3
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.
Topic 4
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.
Example
Cut vertex: in a network of two office LANs joined through one router, the router is a cut vertex — removing it disconnects the network. A single cable joining them would be a bridge.
Exam tip
Vertex connectivity κ(G) ≤ edge connectivity λ(G) ≤ minimum degree δ(G).
Topic 5
Graph colouring and chromatic number
- 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.
Example
Chromatic numbers: a complete graph Kₙ needs n colours; a cycle with an even number of vertices needs 2, an odd cycle needs 3; any bipartite graph needs at most 2. Exam scheduling with conflicting subjects is a colouring problem.
Exam tip
The four colour theorem: every planar graph can be coloured with at most 4 colours.
Topic 6
Planar and connected graphs
- A graph is planar if it can be drawn in the plane without edges crossing; such a drawing divides the plane into regions (faces).
Euler's formula
For a connected planar graph, V − E + F = 2
Edge bound
E ≤ 3V − 6 for a simple connected planar graph with V ≥ 3
Bipartite bound
E ≤ 2V − 4 if there are no triangles
- Kuratowski's theorem: a graph is planar if and only if it contains no subdivision of K5 or K3,3. K5 has V = 5, E = 10 > 3(5) − 6 = 9, so it is non-planar.
- Four colour theorem: every planar graph can be coloured with at most four colours.
Example
Euler's formula: a connected planar graph with 6 vertices and 9 edges has F = E − V + 2 = 9 − 6 + 2 = 5 faces. K₅ (10 edges) breaks the bound E ≤ 3V − 6 = 9, so it is not planar.
Exam tip
Euler's formula: V − E + F = 2. Kuratowski: a graph is planar iff it has no subdivision of K₅ or K₃,₃.
Topic 7
Isomorphism and homomorphism
- Graphs G and H are isomorphic if there is a bijection between their vertices that preserves adjacency. Invariants that must match: number of vertices and edges, degree sequence, number of cycles of each length, connectivity.
Example
A 4-cycle a–b–c–d–a and a square drawn as p–r–q–s–p are isomorphic via a→p, b→r, c→q, d→s. Graphs with degree sequences (3, 2, 2, 1) and (2, 2, 2, 2) are not isomorphic.
- A graph homomorphism maps vertices so that adjacent vertices go to adjacent vertices (not necessarily one-to-one). A k-colouring is a homomorphism into the complete graph Kk.
- Shortest routes
- Maps and navigation (Dijkstra)
- Scheduling
- Exam timetables by colouring
- Networks
- Connectivity and reliability of computer networks
- Circuit design
- Planarity of printed circuits
- Chemistry and social networks
- Isomorphism of molecules, community detection
Key terms
- Degree
- Number of edges incident on a vertex
- Eulerian circuit
- Closed walk using every edge exactly once
- Hamiltonian cycle
- Cycle visiting every vertex exactly once
- Chromatic number
- Minimum colours for a proper vertex colouring
- Planar graph
- Graph drawable without edge crossings
Quick revision
- Directed, undirected, simple, multigraph, complete, bipartite; handshaking lemma.
- Euler: all degrees even (circuit) or exactly two odd (path); Hamiltonian: Dirac and Ore conditions.
- Trees: n − 1 edges, unique paths; spanning trees.
- Connectivity, cut vertices, bridges; colouring, chromatic number, four colour theorem.
- Euler's formula V − E + F = 2; Kuratowski; isomorphism invariants; homomorphisms; applications.
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 path?
- Q3.How many edges does a tree with 15 vertices have?
- Q4.What is the chromatic number of a cycle with 5 vertices?
- Q5.Verify Euler's formula for a cube.
- Q6.State two isomorphism invariants.
Long-answer questions
- Q1.Explain types of graphs and the handshaking lemma.
- Q2.Explain Eulerian and Hamiltonian graphs with examples.
- Q3.Explain graph colouring and planar graphs.
- Q4.Explain graph isomorphism and applications of graph theory.
Stuck on this unit?
Message SBS on WhatsApp for help with Discrete Structures & Optimization, or to ask about studying M.Sc IT at Synetic.
