The test will consist of definitions, examples, algorithms, and proofs, in some combination
which seems possible to do in 75 minutes.

This is more like a reminder of what we've done than a review sheet...but anyway here it is.
I'm just going to list some things.  First, terms you should know how to define and use in a
sentence; second, the major theorems and facts that we've discussed; and third, algorithms
that you should be able to execute.

Terms you should know:  this is a long list.  At the beginning, most of them are completely
straightforward.  There are some, however, which are more conceptual.  You might have
different opinions about which ones, but the ones that I thought required some thinking to
digest I marked with a *.
    Graph, vertex, edge, adjacent, incident
    Multiple edge, loop, simple graph
    Degree, end-vertex, isolated vertex, degree sequence
   *Isomorphism:  this is a kind of function
   *Isomorphic:  a relation which may or may not hold between TWO graphs
        (the sentence "G is isomorphic" makes no sense)
    Connected graph, connected components of a graph
    Subgraph, G-v, G-e, G\e
   *Complement of a graph
    Adjacency matrix
    Path graph, cycle graph
   *Bipartite graph
    Complete graph, complete bipartite graph
    Cube graph
    Regular graph
    Platonic graphs, Petersen graph
   *Walk, length of a walk, trail, path, cycle
    Cutset, bridge, *edge-connectivity
    Separating set, cut-vertex, *vertex-connectivity
   *Eulerian and semi-Eulerian graphs: remember the difference between the definition and
        the theorem...the definition is that there's a certain kind of trail in the graph
   *Hamiltonian and semi-Hamiltonian graphs
    Tree, forest
   *Spanning tree of a graph
   *Planar graph, planar drawing of a graph
   *Homeomorphism, contraction:  think of each of these as a process
   *Homeomorphic, contractible:  relations which may or may not hold between TWO graphs
        Note that if G and H are homeomorphic, then H and G are homeomorphic.  HOWEVER,
        If G is contractible to H, it does not mean that H is contractible to G.
   *Genus of a graph
    Crossing number of a graph

Major theorems and facts you should know how to prove:
    The handshaking lemma
    A graph is bipartite if and only if all its cycles have even length
    A graph is Eulerian if and only if all its vertices have even degree  (This isn't a definition, it's
        a theorem)
    A graph is semi-Eulerian if and only if exactly two vertices have odd degree  (same here)
    Ore's theorem:  a sufficient condition for a graph to be Hamiltonian
    Various characterizations of trees:  see Theorem 9.1 in the book
    How many labeled trees on n vertices are there?  n^(n-2)
    A graph is planar if and only if it contains no subgraph homeomorphic to K₅ or K_3,3
    Above is true if "homeomorphic" is replaced by "contractible"
    Euler's formula:  v-e+f=2 for any planar drawing of a connected (planar) graph
    Euler's formula for surfaces:  v-e+f=2-2g (where g is the genus)
    For any graph G, its genus is less than or equal to its crossing number
    There are only five Platonic solids

Algorithms you should be able to implement:
    Given an Eulerian graph, find an Eulerian cycle
    In a weighted graph, find the shortest path from one vertex to another
    The Chinese postman problem:  find the shortest walk which uses every edge at least once
        You should be able to do this in some simple cases
    The travelling salesman problem:  find the shortest path which uses every vertex at least once
        Again, you should be able to do this in some simple cases
    Given a weighted graph, find a minimal weight spanning tree (the greedy algorithm works)

I think that's about it.  There are some minor lemmas too, like the one that says that if a graph has
no vertices of degree 1 then it must contain a cycle, and things like that.