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.