Week 3 - Spanning Trees and Kruskal's Algorithm

This week we will be finishing up the graph theory material with a discussion of trees and spanning trees. A tree is just a connected graph which contains no circuits. We will be concerned with finding subgraphs of graphs which contain all the original vertices and are trees. These are called spanning trees. Kruskal's algorithm gives us a way to find a spanning tree of minimal weight in a weighted graph. This algorithm should feel familiar to you; it is very similar to the Side Sorted Algorithm, except now our goal will be to end up with a spanning tree rather than a Hamiltonian circuit.

Exam 1 will be in class on Monday, February 6.  Make sure to bring your graded worksheets to class with you on Monday to turn in.  I have posted an exam review on the right hand side of the blog and below.  Please print this out and bring it to class with you on Wednesday February 1.  (Don't forget you must be logged in to your MWSU email account to access this.)

Graph Theory Exam Review


Challenge Problem: A connected graph G has 18 vertices. How many edges does a spanning tree of G have? How many vertices does a spanning tree of G have? What can one say about the number of edges G has?

Beginning of the year survey

Please fill out the survey below honestly.  You must be logged into your Missouri Western account to access the survey, but your answers will be collected anonymously.

Graph Isomorphisms and Making Mistakes

I've received several questions about problems 12 and 13 in the first WebWork graph theory assignment.  These questions give you a graph and ask you to determine which of the three graphs below is the same graph, represented differently.  It then asks you to give the one-to-one correspondence that identifies the two graphs.  This correspondence is called a graph isomorphism.  These problems can be tricky, and require some thought and creativity to find the right correspondence.  However, it's a valuable exercise to struggle with problems sometimes, and it makes finding the right solution all the more sweet!

Imagine if you had to do this same thing, but for a graph with thousands of vertices!  It might be a daunting task to imagine.  Of course, you wouldn't want to have to try to find this isomorphism by hand, but even asking a computer to do this would be difficult.  In fact, recent research has been trying to determine if there is a way to determine if two graphs are isomorphic "quickly".  A computer scientist, Laszlo Babai, from the University of Chicago, announced in November 2015 that he had found an algorithm to determine if two graphs were isomorphic in quasipolynomial time.  But, earlier this month, another mathematician,  Harold Helfgott, posted that he had found an error in the proof.  It can be frustrating for you to find that you've answered a problem incorrectly in MAT110(E); imagine if you had announced to all of your colleagues that you had solved a problem, only to find that your solution was incorrect.  This happens to mathematicians all the time.  (I, too, have submitted a paper to a mathematics journal claiming to have proven something, only to find that there was a subtle error in my reasoning.  I've still been unable to correct my error!)  Even when we get the answer wrong, there is value in the struggle that it takes to work with a problem.  Maybe those skills that you learned to work with this problem will help you with a problem in the future.  Maybe you'll remember how to correct it just a little bit better because you had to struggle to find the right answer.  Don't focus too much on worrying about making mistakes - everyone will make them - instead, make sure you learn from your mistakes and are ready to apply what you learned in the struggle to the next problem.

Don't worry about Babai - he's corrected the problem in his algorithm.

You can read more about graph isomorphisms and Laszlo Babai's algorithm at the American Mathematical Society's blog on math and the blog Computational Complexity.

Week 2 - Fleury's Algorithm and Hamiltonian Circuits

This week we will be finishing up with Euler circuits and moving into Hamiltonian Paths and Circuits and weighted graphs.  Fleury's algorithm will give us a systematic way to find an Euler circuit in a graph that contains one.  Not every graph has an Euler circuit, but we can Eulerize a graph by duplicating existing edges in such a way that the resulting graph contains an Euler circuit.  Why do you think it might be useful to Eulerize a graph?

A weighted graph is just a graph with numbers (weights) on the edges.  Our goal will be to use weighted graphs and Hamiltonian circuits to solve the Traveling Salesman Problem.  We will see three algorithms for solving this: The Nearest Neighbor Algorithm, The Side-Sorted (or Best Edge) Algorithm, and the Repetitive Nearest Neighbor Algorithm.  We will also discuss how to solve this using Brute Force.  You will need to memorize each of these algorithms.  

Don't forget to keep up with the homework on WebWork and the associated worksheets.  Once you complete a worksheet, you should take it to the CAS to grade and correct your work.  I will collect all the graded/corrected worksheets in class on the day of the unit exam.

Challenge Problem: (Due Monday, January 30) The picture below is the floor plan for the Plaza Level of the Nelson-Atkins Museum in Kansas City.  Doorways are represented by a break in the wall.  Is it possible to start in one room on this floor, travel through every doorway, closing the door behind you, and return to where you started?  Use graph theory to answer this question.  Your solution should include a graph, explain how the graph is related to the floor plan, and explain how you used graph theory to determine if such a path exists.  If the path exists, give it; otherwise explain why it is not possible.

http://www.nelson-atkins.org/visit/map/

How to Email Your Professor

Every semester, I receive an email that looks something like the following:

hey mrs. mccune.  did i miss anything important in class today?  also, i don't know how to do number 2.

There are several issues with this email.  First, you should address your instructors as Professor or Dr, unless they have asked to be addressed differently.  (I am Dr. McCune.)   Second, if you must miss class, please acknowledge that you are responsible for the material covered in your absence.  I am happy to give a brief recap of what you missed, but please remember to first consult the syllabus and the notes before composing your email.

If you need help with a specific homework problem, please be clear about which problem you need help with.  For example, "I need help with number two on the webwork Graph Theory set 1". You should tell me what you've tried so far and specifically what part of the problem is giving you trouble.  It is often useful to include an attachment with a picture of your work so that I can best point you in the right direction to solve the problem. 

Finally, be sure to sign your email with your name, course number, and section.  It is especially difficult to respond to an email if I don't know who the sender is.

Wikihow has a nice summary of how to email a professor, which you should apply when emailing any of your professors on campus.

How to Email a Professor

Week 1 - Welcome to MAT110(E)

Welcome to MAT110/MAT110E! You should be enrolled in MAT110 if you have a 22 or higher on the ACT or passed the math placement exam (MPE) with a 70 or higher. Otherwise, you should be enrolled in MAT110E and MAT099. Keep in mind that if you fail MAT099, you will fail MAT110E as well, regardless of your exam and homework scores in MAT110E. Hence, it is imperative that you attend and actively participate in your MAT099 section.


Our semester will be broken into three major units: Graph Theory, Financial Math, and Probability and Statistics.  We will have a fourth shorter unit over Voting Theory at the end of the semester.  I hope that you will enjoy learning a little bit about each of these topics and how they are used in your everyday life and the world around you. I'm looking forward to a great semester!


We will be kicking off the semester this week with an introduction to graph theory. A graph is a collection of vertices (think dots) and edges (think lines) between the vertices. We can use graphs to study many things in the world around us. For example, a graph can represent streets and intersections from a map (see The Traveling Salesperson Problem), computer networks, social networks, or even be used to study DNA (see A Graph Theoretical Approach to DNA Fragment Assembly). By the end of this week, you should know what a graph is and be able to describe several properties of a graph. 

A little bit about me: I am in my fifth year as an Assistant Professor of mathematics here at Missouri Western State University. Before coming to MWSU, I spent a year as a visiting assistant professor at Ashland University. I received my PhD from the University of Nebraska-Lincoln in 2011. (Go Big Red!) My husband is also a mathematician at William Jewell College. We have a 2.5 year old daughter and a 9-month old son who are both a bundle of energy. 

Please ask for help as soon as you are having trouble with this class. You can visit me in my office (Agenstein 135K). Peer tutoring is also available (for free) through the Center for Academic Support.

Challenge Problem #1: (Due at the start of class on Monday, January 23) Sketch several examples of graphs. Determine the degree of the vertices in each graph. When you add the degrees of all the vertices, you will always get an even number. Why is that?