**MATH241. Discrete Structures 2**

### Calendar description

**MATH 241 Discrete Structures 2**(3 credits) (Prerequisites: MATH 240 or
MATH 235. Not open to students who have taken or are taking MATH 343) Review of
mathematical foundations and logical reasoning. Undirected and directed graphs:
motivation, history, applications and theory. Eulerian circuits, trees.
Introduction to bipartite graphs, tournaments, connectivity, planarity,
distances in graphs, directed acyclic graphs, graph colouring, applications of
graphs to probability.

### Summary

MATH241 is a sequel to MATH240. Like the earlier course, the emphasis is as
much on mathematical skills and the development of mathematical maturity as it
is on the actual topics covered. In this course, students will develop further
skills in problem solving, proof writing, and presentation of mathematics. The
bulk of the material in the course is from graph theory. Students will build on
experience gained in MATH240, and practice writing both verbal and non-verbal
proofs, as well as proofs that involve more complex logic and structure.

Like MATH240, the course begins with a discussion of mathematical logic,
reviewing and formalising material in logic covered in the earlier course.

The course then presents basic material in graph theory. There are many
different ways to present this material, and several good texts available, so we
only give broad outlines. We have listed a number of topics and
applications.

### List of topics

What follows is a relatively high level list of topics. Most of the later
topics and applications can be included or excluded in response to demand.

**Mathematical logic and mathematical writing**. Review of material in
240. An introduction to a formal approach to logic.
**Undirected graphs** Basic definitions. Paths, trails, cycles and
circuits.
**Directed graphs** Basic definitions. Paths trails, cycles.
**Trees** Characterisations. Rooted trees. Spanning trees.

An introduction to the following:

**Bipartite graphs** Characterisations. Applications.
**Connectivity in graphs** Bi-connectivity, k-connectivity, cuts.
**Connectivity in digraphs.**
**Planar graphs** Definitions. Eulers formula. Applications.
**Distances in graphs.**
**Graph colouring** Definitions and upper bounds. The 6,5,4 colour
theorems.
**Tournaments.**
**Directed acyclic graphs.**
**Graphs and probability** Transition matrices. Markov chains. Random
walks.