Graph theory paper
Your assignment is to write an expository article on a topic related
to the subject matter of our course, graph theory and discrete
mathematics, but not substantially overlapping the material covered in
class. You should formulate your paper around a single, interesting,
focused idea in mathematics or theoretical computer science, including
an explanation in your own words of the proof of a theoretical result.
Write your paper for an audience of other MCS 236 students. In other
words, assume that your audience has the same general knowledge and
interests as you do, but is not necessarily well informed about your
topic. Strive to capture the reader's interest and to hold it, and
strive for clarity and a natural flow in your exposition of the
technicalities of your topic.
The paper should discuss the proof of a theoretical result. State at
least one relevant theorem to your paper, and prove it in your own
words. If a theorem is too technical to prove in the context of a
5-10 page paper, then state the theorem and explain something related
to it. Possibilities include:
- a related theorem (with proof)
- the proof of some lemma(s) used to prove the theorem
- as a last resort, a clear discussion explaining why the theorem is
important may have to suffice.
Your paper should be about 5-10 pages long. It should be typed, but
you may include handwritten formulas and hand-drawn diagrams.
- Ideally, a topic of your choosing, approved by me. The topic can
be outside of graph theory if it has something to do with
mathematics in computer science. Many citations in the text
provide a good starting point. You can find graph theory in
every area of computer science.
- The four-color theorem with proof that any planar graph can be
- Graph coloring approaches to register assignment
- Traveling salesman problem
- How Internet search engines use graph theory
- Alpha-beta pruning for games
- Other search techniques for games such as Chess
- Huffman codes, and their use in other data compression codes
- Expander graphs
- Stable matchings used in matching students to medical residencies
- Heuristics for drawing graphs on a computer screen
- Some graph algorithm(s) used in Computer Aided Design (CAD)
You will be assessed primarily on your ability to argue a clear and
appropriate thesis that focuses on the differences and/or similarities
in values of the two cultures and your effective use of sources. For
this particular paper, I will use the following grading guidelines.
(These guidelines are taken nearly verbatim from Lewis Hyde.)
- The F paper is rare. This grade is usually reserved for cases of
plagiarism and excessive lateness. However, exceptional failure to
comply with the terms of an assignment may also result in an F.
- The D paper, in some significant way, doesn't answer the question
that was asked. It lacks a thesis or an argument, or it has a thesis
which is inappropriate to the assignment. A D paper which does answer
the question is filled with mechanical faults (errors in grammar
and/or spelling). Paragraphs do not hold together; ideas do not
develop from sentence to sentence. This paper usually repeats the
same thoughts over and over, perhaps in slightly different language
but often in the same words. It is usually rambling and
- The C paper has a thesis which is vague and broad, or which
answers only part of the question(s) asked; or it may make a good
argument without first offering a thesis statement (usually in the
introduction). The C paper rarely uses evidence well; sometimes it
uses no evidence at all and relies entirely on unsupported personal
opinion. Even with a clear and interesting thesis, a paper with
insufficient supporting evidence is a C paper. Sometimes a C paper
has a good deal of evidence, but it is not part of a coherent argument
and the reader can only make sense of it with great difficulty (if at
all); thus, the evidence is ineffective. This paper may not
effectively address core graph theoretic issues in your topic.
- The B paper makes sense throughout. It has a thesis that is
appropriate, complete and worth arguing. It does not digress, and it
ends by keeping the promise it made to the reader in the beginning.
The reader always knows where the paper is going and what the author
wants to say. The paper presents interesting ideas, supported with
sound evidence which is both to the point and well documented. This
paper effectively addresses cultural values related to the particular
The paper is well organized and although some sentences may not be
elegant, the ideas in them flow well and thought naturally follows on
thought. The paragraphs may be unwieldy now and then, but they are
organized around one main idea. The reader does not have to read a
paragraph two or three times to figure out what the writer is trying
The B paper is, for the most part, mechanically correct. There will
be occasional spelling and grammar errors, but these are few in number
and do not prevent the reader from following the ideas in the paper.
- The A paper is rare. It has all the qualities of a B paper,
but in addition it is lively, well paced, interesting, even exciting.
Everything in it seems to fit the thesis exactly. The paper has
style. Reading this paper, the reader feels a mind at work. The sure
mark of an A paper is that the reader continues to think about it
after reading it, even wanting to tell others about it.
This paper may have a proofreading error or two, even occasional
misspelled words or a minor error in grammar, but these errors are the
consequence of the normal accidents all good writers encounter.
In this assignment, an A paper teaches me something I didn't already
know before I read the paper.
Citations and bibliography
Any statement you make which isn't common knowledge or which isn't
argued within your paper should include a citation (see Hacker).
Common knowledge is any knowledge which you might expect a typical
member of your audience (in this case, a classmate) to have.
Your paper should not rely on just one source unless it is a book
In your bibliography, in addition to Hacker's guidelines, add one
sentence to each references which explains to the reader why
the source is (or is not) reputable.