## Outline of IB Maths HL option Discrete mathematics

Strong induction, Pigeonhole principle, Degree sequence, Handshaking lemma, Tabular representation of graphs, Solution of 1st and 2nd degree linear homogenous
recurrence relations with constant coefficients, The first degree linear recurrence relation, Modelling with recurrence relations, Adjacency tables, Chinese postman problem

### Outline of IB Maths HL option Discrete mathematics

Outline of IB Mathematics Higher Level- Option: Discrete mathematics

Here you can find a description of the course not so detailed.
You can find the official syllabus of IB maths SL on the following link of IBO
http://www.ibo.org or http://store.ibo.org

Strong induction. Pigeon-hole principle. Division and Euclidean algorithms. The greatest common divisor, gcd(a,b) , and
the least common multiple, lcm(a,b) , of integers a and b.
Prime numbers; relatively prime numbers and the fundamental theorem of arithmetic.
Linear Diophantine equations ax + by = c
Modular arithmetic. The solution of linear congruences. Solution of simultaneous linear congruences (Chinese remainder theorem).
Representation of integers in different bases.
Fermat’s little theorem. Graphs, vertices, edges, faces. Adjacent vertices, adjacent edges. Degree of a vertex, degree sequence.
Handshaking lemma. Simple graphs, connected graphs, complete graphs, bipartite graphs, planar graphs; trees, weighted graphs, including tabular representation. Subgraphs; complements of graphs. Euler’s relation, theorems for
planar graphs. Walks, trails, paths, circuits, cycles. Eulerian trails and circuits. Hamiltonian paths and cycles.
Graph algorithms: Kruskal’s; Dijkstra’s. Chinese postman problem. Travelling salesman problem. Nearest-neighbour algorithm for determining
an upper bound. Deleted vertex algorithm for determining a lower bound.
Recurrence relations. Initial conditions, recursive definition of a sequence. Solution of first- and second-degree linear
homogeneous recurrence relations with constant coefficients. The first-degree linear recurrence relation.
Modelling with recurrence relations.
ib maths