One of the most widely used structures in mathematics and applications is a graph. Here we don’t mean the graph of a function, but rather a diagram that you can draw with points (vertices) and segments (edges). Graphs can be used to model networks such as a transit system or even social media Friends. Many of the most important algorithms used in computing operate on data stored in a graph structure. We introduced graphs and some key terminology we use to talk about them.

In the second half of the lesson we studied cycles in graphs, which are paths through the edges of the graph that start and end at the same vertex. An Euler cycle is one that touches every edge once, and a Hamilton cycle is one that touches every vertex once. When does a graph have an Euler cycle? When does it have a Hamilton cycle? We tried it out with a number of sample graphs, and looked for patterns in the results.

Handouts from the session