Discrete Math - Following Counting with Graph Theory

As in past years, I started my discrete math class with the unit on counting. This unit tends to be cerebral as their is a lot of looking at and understanding patterns coupled with complex reasoning. I was then following the counting unit with a unit on number theory and cryptography, which tends to be more of the same in terms of a lot of intense reasoning and pattern recognition.

This year I decided to follow the counting unit with a unit on graph theory. I wanted to switch the order partly because I wanted to cover a bit more in graph theory than I had time for in the past. The other reason was seeing more connections between counting and graph theory.

The unexpected benefit of this change is that the graph theory unit is much more of a hands-on unit, where students draw graphs and have physical models with which to work. This is a break from the more abstract activities in counting or number theory. The class energy has risen considerably along with better engagement.

I am still fleshing out how the entire graph theory unit will play out but the major points to cover are:

• Euler paths and circuits
• Hamiltonian paths and circuits (covering existence theorems without delving into TSP)
• Planar graphs including 
• Complete and complimentary graphs
• Proofs with graphs

I still need to gauge how much time to use and still leave enough time to adequately cover number theory and cryptography.

As I finalize the extended graph theory unit I will post an unit outline.

Discrete Mathematics Probability Revisions

I decided to make some changes in the order of presentation after teaching the probability lessons at the end of the counting unit. The particular lesson that I revised dealt with the discussion of discrete probability, uncovering probability rules, and working through examples.

What I found was that having students discuss what they knew about probability before working through the practice problems is that the class floundered because they lost site of the counting aspect of the problems and tried to make use of more familiar probability rules.

The three problems the class worked on were:

                                                                      i.      Probability dealt a black-jack

                                                                    ii.      Probability dealt a flush

                                                                  iii.      Probability dealt the queen of spades when four people playing hearts

I intend to have students use their counting techniques exclusively to find these probabilities before
diving into probability rules they may know. I can then connect their known rules back to these 
problems to show have they manifest themselves.

Here's the outline for having students go through probability rules:

     i.      Have students create list of rules they know
          1.      Rules to have
               a.      P(A or B) = P(A) + P(B) for mutually exclusive events
               b.      P(A and B) = P(A) x P(B) for independent events
               c.       0 <= P(A) <= 1
               d.      P(not A) = 1 – P(A)
               e.      sum of all probabilities = 1
               f.        may be others
          2.      Share out list and discuss
          3.      Students create examples of each rule using playing cards
               a.      Share and discuss

          4.      Cover additional rules not previously identified
          5.      Discuss connections between rules and the three problems previously worked on