Petersen graphs Herschel graph Clebsch graph

Task:
Learn a new theorem about a numerical graph invariant and communicate it in written form.
Minimum requirements:

  • Each student will focus on a different numerical graph invariant.
  • The written document will introduce, correctly state, and prove a theorem. It will also include at least one interesting example illustrating the theorem. The article will be as self-contained as possible. The new document must be typed, be at most eight pages in length (with one inch margins and a 12pt font), and be available in PDF format.
Assessment and deadlines:
Project grades will be computed as follows:
due date element weight
2012-10-10 outline 10%
2012-11-07 rough draft 20%
2012-11-14 feedback 20%
2012-11-28 final paper 50%
Advice:
Here are some suggestions on how to present mathematics: Halmos on writing and Kleiman on writing.
Comments:
By design, this assignment is very open-ended. Students are strongly encouraged to compute many examples. Students are also encouraged to formulate, test, and prove their own conjectures. Here are some questions that you may want to consider:
  • Can your numerical graph invariant be calculated for any graph, or does it only apply to certain graphs?
  • Can you bound your numerical invariant?
  • Can you describe the set of graphs with a given numerical invariant?
  • How is the numerical invariant of a graph related to its subgraphs or minors?
  • Is your notion of your numerical invariant particularly well-adapted for some application?
Potential topics:
The following numerical graph invariants (or simple formula involving them) are natural candidates: