Edging Coloring Complete Graphs – Two Examples

Dr. John Caughman from Portland State University presented our Kieval Lectures this year.  He described rainbow graphs and matching, rectangle graphs and lattice paths. I intended to take notes because of past experience but I got so interested that I just went with the flow.  Dr. Caughman is an engaging humorous speaker.  His material was accessible to our students and was well received.  It was very stimulating to think along with his discussions.

One of the concepts was something called rainbow graphs.  I could have spent a little time on the net looking for precise definitions and theorems, but I thought to have fun with my own explorations.

Using Mathematica I tried to create symmetric edge colorings (no edges of the same color meet at the same vertex) of complete graphs that resulted in “nice” matchings.  I used an idea Brian Stonelake suggested of putting a complete graph “inside” or “above” another complete graph of the same size (matching requires an even number of vertices).  I used three dimensions to help me visualize.  The upshot is the two images below and my greater understanding of the intricacy of one aspect of graph theory.

Complete Graph with Six Vertices

Complete Graph with Six Vertices

Complete Graph with Eight Vertices

Complete Graph with Eight Vertices


About jrh794

I am a sixty-five year old math instructor at Southern Oregon University. I taught at the College of the Siskiyous in Weed California for twenty-six years. Prior to that I worked as a computer programmer, carpenter and in various other jobs. I graduated from Rice University in 1967 and have a MS in Operations Research from Stanford. In the past I have hand-built a stone house and taken long solo bicycle tours. Now I ride my mountain bike and play golf for recreation.
This entry was posted in Cool Ideas, Math Explorations and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s