Graph Theory Review Sheet Template printable pdf download

Fall 2013

Exam 4 Review

Math 111

Here is a mostly complete list of topics and concepts we have covered related to Graph Theory.

Deﬁnitions

(You won’t be asked to deﬁne anything speciﬁc on Exam 4, but you should have a pretty good working

knowledge of the deﬁnitions below.)

Basics: Be able to identify vertices and edges. Be able to create a graph given information about

the vertices and edges. Know that the word “order” corresponds to the number of vertices in a given

graph.

Isomorphic Graphs: Be able to tell when two graphs are (or are not) isomorphic. Be able to describe

an isomorphism (correspondence of vertices) for isomorphic graphs.

Connected: Know what a connected graph is and what the term “component” means.

Chromatic Number (or -colorable: Know what these terms mean and how to ﬁnd them for a given

graph.

Planar Graphs: Know how to determine if a graph is planar, and what this means. Know how to ﬁnd

the number of faces for a planar graph. Know how to ﬁnd the degree of a face.

Cycle: Know what a cycle is and how it can be useful.

Euler Circuits: Know what these are and how to recognize them in applications.

Euler Trails: Know what these are and how to recognize them in applications.

Important Theorems

Sum of The Degrees (Vertices) Theorem: Know what this means and how you can tell if a list of

degrees corresponds to an actual graph.

Sum of The Degrees (Faces) Theorem: Know what this means and how to use it.

Euler’s Formula: Know how to use this formula for all variations of questions we have discussed.

Chromatic Number One Theorem: This one is easy to recognize.

Chromatic Number Two Theorem: Know how to discuss when a graph has Chromatic number 2 by

considering cycles.

4-Color Theorem: Know which graphs this theorem applies to. Know which applications this theorem

applies to (because of the corresponding graphs).

Euler’s Circuit Theorem: Know how to tell if a graph has an Euler Circuit or not.

Euler’s Trail Theorem: Know how to tell if a graph has an Euler Trail or not.

Graph Theory Review Sheet Template