Graph theory paper

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.

Possible topics

• 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 five-colored
• 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)

Grading guidelines

• 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 directionless.

• 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 topic.

  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 to convey.

  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

Your paper should not rely on just one source unless it is a book report.

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.