MATH 412 - Graph Theory

Homework Advice

Based on what I see in the homeworks I have received, I collected the following list of advice for your homework preparation. Some of these bits are major (as in, you will lose points if you do not follow them) and others are minor. However, your homework scores will improve if you follow these guidelines and your proof writing skills will improve.

As the semester continues, I will add more advice so you are expected to check this page before finishing any assignment.

Organization

Please start each problem at the top of each page and present the problems in order. Staple the pages together. Your name should be at the top of every page and not under the staple

If the proof of a statement requires proving several smaller facts, list those facts and prove them in different paragraphs. This includes the necessary and sufficient directions of characterization proofs.

If there is a fact that you use multiple times, list it as a lemma in whatever generality you require and prove it before continuing to the rest of the argument. Be sure the statement of the lemma is flexible enough to be used later.

To ensure proper organization, you should re-read and re-write your arguments at least once! If you simply check your work once, you'll find awkward language, logical jumps, and other errors which would otherwise cause loss of points.

Your handwriting should be easy to read. Also, your writing utensil should be appropriate. If you use pen, there should not be scratches crossing out arguments. If you use pencil, the writing should be dark enough to read. If you type your solutions, use at least 12pt font.

Keep it short. The problems assigned have proofs which fit in a single page with reasonable handwriting (or half a page typed. If you cannot fit your argument in a single page, consider if your argument can be tightened or if there are sentences that can be removed.

Every sentence should have a point that is crucial to the argument holding. Do not include "side facts" that you discover while searching for the proof. This only clutters the page and makes grading more difficult. (If you do find these facts, feel free to include the statements (not proofs) of them after the problem solution.)

Every statement should be true and be true due to an argument. When re-reading your proof (yes, you should read your proof multiple times and rewrite your proof multiple times) ask yourself 1) is this sentence required to prove the statement? and 2) is the truth of this sentence fully explained?

Do not include scratch work with your final solutions. Think of each assignment as a final draft as a report. It should not be your first (or even second, probably) draft.

Arguments

An "if and only if" statement requires both directions: necessity (only if) and sufficiency (if). They can appear in any order, but you should clearly label which direction you are proving and each part should be a separate paragraph.

You should be able to know when you are wrong. If you can't tell when your proof is incorrect, then you can't tell when it is right, either. It is better to identify gaps in your argument (as in "I want to use this to build a bipartition, but I don't know how") than to write nonsense.

If there is a concept or structure that you use several times in your argument, make a new definition that is clearly stated and use it when required. This can significantly clarify and shorten your argument.

When showing there exists some substructure, you must show both how and why: how can you find or build the substructure? Why does that substructure satisfy the properties required? Without both of these steps, your argument is incomplete.

When you use induction, clearly state what parameter you are inducting on, such as the length of a path, or the size of a graph. Without this parameterization, there are chances that you make a mistake in your induction step.

f you write "It is easy to see that" or "Clearly, ..." you should present the reason why it is true, since it is so "ea sy". In the context of lecture, this may be appropriate, but for assignments you must demonstrate understanding and not rely on the instructor's power of deduction.

When building an argument, refer to the definitions involved. This will both help you with what structure you have at your disposal and what structure you are trying to find. If you have a decomposition, use the fact that decompositions cover each edge exactly once. If you are building a bipartition, show that each partite set is independent.

Be aware of the difference between maximal and maximum or minimal and minimum. A maximal object is one that is not properly contained within another object of that type (so, a maximal path is not a sub-path of another path) but a maximum object has the largest value of some parameter over all objects (a maximum-length path of a graph has the longest length over any path in the graph). A maximum object is by necessity maximal, but not the other way around. Sometimes maximal suffices but other times maximum is required. Be sure to use the correct one. Similar advice holds for minimal/minimum.

Grammar

The singular of vertices is vertex. Do not write "vertice" as it is not a word. Also, see leaf/leaves, matrix/matrices.

When picking a letter for an object, try to avoid letters which normally represent other things: $e$ is usually and edge, $n$ is the number of vertices, $V$ should be a vertex set and $E$ should be an edge set. $d$ is usually a degree (but when preceded by vertices $a$, $b$, and $c$, it is okay as a vertex).

Contractions (aren't, don't, won't, can't) are too informal for proofs. They should be avoided.

Avoid pronouns as they only cause confusion. Avoid "it" or "this" or "that" especially.

If you want to improve your grammar for graph theory, see the Grammar According to West, written by the textbook author. There are a lot of things in there, some of which are not immediately relevant to MATH 412. However, I highly recommned the "English usage" and "For Non-Native Speakers" sections as they are useful even when writing other types of mathematics.