Mathematical Background:
   Sets
   Induction and recurrence
   Functions
   Counting
   Relations

1.1 What is a graph
    Definitions
        graph, clique, independent set, complement, bipartite,
        chromatic number, path, cycle, subgraph
    Matrices and Isomporphisms
        adjacency matrix, (incidence matrix), isomorphism is a
        bijection, isomorphism is an equivalence relation, complete
        graph Kn, complete bipartite graph Km,n
    Pk, Ck, Kmn, Girth of a graph, Petersen graph

1.2 Paths, cycles, trails
    Induction
    Connection in graphs
      walks, trails, length of a walk, closed
      LEMMA:  Every u,v-walk contains a u,v-path
      connected vs adjacent, component graph
      cut-edge, cut-vertex, induced subgraph
      THEOREM:  An edge is a cut-edge if and only if it belongs to no cycle
    Bipartite graphs
      LEMMA:  Very closed odd walk contains an odd cycle
      THEOREM: A graph is bipartite if and only if it has no odd cycle
    Eulerian Circuits
      LEMMA:  If every vertex of a graph G has degree at least 2, then
              G contains a cycle.
      THEOREM:  A graph G is Eulerian if and only if it has at most
          one nontrivial component and its vertices all have even degree.
      Proposition: Every even graph decomposes into cycles
      Proposition: If G is a simple graph in which every vertex has
          degree at least k, then G contains a path of length at least
          k.  If k >= 2, then G also contains a cycle of length k+1.
      Proposition: Every graph with a nonloop edge has at least two
          vertices that are not cut-vertices.
      Lemma: In an even graph, every non-extensible trail is closed.
      Theorem:  For a connected nontrivial graph with exactly 2k odd
          vertices, the minimum number of trails that compose it is
          max{k,1}
    

1.3 Vertex Degrees and Counting
    Counting and bijections
      Degree, minimum degree little-delta, maximum degree big-delta,
              neighborhood N(v) 
      Order of a graph n(G) and size of a graph e(G)
      PROPOSITION: If G is a graph, then the sum of the degrees is 2e(G)
      Structure of the hypercube
    Extremal problems
      PROPOSITION: The minimum number of edges in a connected graph
                   with n vertices is n-1 
      PROPOSITION: If G is a simple graph n-vertex