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