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
- Euler circuit
- Uses every edge once: all degrees even
- Hamiltonian cycle
- Visits every vertex once
- Chromatic number
- Fewest colours with no adjacent pair alike
- Planar graph
- Drawn without crossing edges: V − E + F = 2
- Isomorphic graphs
- Same structure, different labels
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.
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
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.
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.
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.
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.