MAT2540/D670 – Discrete Structures II

Suman Ganguli | Spring 2025

Page 3 of 7

Class 18 Recap (Wed April 2)

We continued discussing Sec 10.2, specifically “special” types of graphs (complete graphs K_n, cyclic graph C_n, “wheels” W_n), and bipartite graphs. We also did a quiz, covering some of the basic terms and ideas from Sec 10.1.

Please continue working on HW#3, which is due next Wednesday (April 9 — which is the last class before Spring Break); note that I added a couple more Sec 10.2 exercises (in bold) to the previously announced list:

  • Sec 10.1: #3-9
  • Sec 10.2: #1-4, 7-9, 12, 20, 21-23

The slides for Ch 10 are available as a pdf in OpenLab Files.

We will have another short in-class quiz on Monday, which will cover some more of the basic concepts from Sec 10.1 and 10.2 (similar to the HW exercises). I will also accept any additional Exam #1 corrections on Monday.

(You can see the page I showed about the “Hub-spoke network topology in Azure“; you can also look at the wikipedia page for “Spoke–hub distribution paradigm“)

Videos: Graph theory

Some videos on graphs and graph theory:


A short video about the historical origins of graph theory, with the “Seven Bridges of Königsberg” problem that the famous mathematician Leonhard Euler investigated in the 1730s:

Another couple of videos (from a YouTube channel that has a Discrete Math course playlist!) that introduce graph theory and does more of the math involved with the Bridges of Königsberg, introducing the idea of Euler paths and Euler circuits:

Here is a video introducing “the traveling salesmen problem”–a famous and important “optimization” problem in graph theory that has led to a lot of work in computer science (there are entire books about it–a good introductory one that is available online via the CityTech Library is In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation) by William Cook:

That YouTuber (MinuteMath) has multiple videos about graph theory–here is an introductory one:

A video on how map apps (e.g. GoogleMaps) find the shortest route (through a graph!):

[I will add more videos to this post — if you find good videos, please post them in the comments below!]

Class 16-17 Recaps (Mon March 23 & Wed March 26)

We continued discussing Sec 10.1 and 10.2, introducing the basic concepts about graphs.

Please continue working on HW#3:

  • Sec 10.1: #3-9
  • Sec 10.2: #1-4, 7-9, 12, 20, 21-23

The slides for Ch 10 are available as a pdf in OpenLab Files.

The college is closed on Monday, March 31, so our next class meeting is Wednesday, April 2.

We will have a short in-class quiz on Wednesday, which will cover the basic concepts from Sec 10.1 and 10.2 (similar to the HW exercises). I will also collect any Exam #1 corrections on Wednesday.

Monday, March 23:

Wednesday, March 26:

« Older posts Newer posts »