Reducibility Algorithm

-induction on edges

 

Objective::

Students will be exposed to an inductive argument to solidify the algebraic/deductive argument using counting methods.

Materials :

Lesson:

During the second day of the Algebraic/deductive argument involving counting methods, walk through the induction on edges proof with the students. Pay close attention to new vocabulary {Jordan curve, isolated vertex etc.} Use a sketch pad animation to illustrate the contraction and removal of edges.

Assignment:

Work with Geometer's Sketchpad to create a script for edge removal as well as removal of a Jordan curve. This is difficult to manage, be sure to notice students drawings that change shape creating new vertices or faces when dragging vertices in order to eliminate an edge and a vertex.

Example draw using GSP


Back to the Discrete Mathematics and Graph Theory Introduction

Lisa's Home Page