Discrete Math II Math 852 Spring 2013 Class Log

 1. Jan 7, Mon. course overview and logistics; initial student survey; Sec 5.1: basic concepts in graph theory; definitions, isomorphism, subgraph and induced subgraph; common graph families; Petersen graph 2. Jan 9, Wed. cartesian (box) product; hypercube; Sec 5.2: degree sum formula; counting nested subgraphs; application to the number of 5-cycles in Petersen graph; degree sequences; characterization for multigraphs allowing loops; graphic sequences; statement of Havel-Hakimi; easy direction 3. Jan 11, Fri. proof of Havel-Hakimi; 2-switches; can transform between graphs with same degree sequence using 2-switches; every graph has a bipartite subgraph with at least half the edges; maxmimum number of edges in a triangle-free graph 4. Jan 14, Mon. proof of Mantel thm; basic definitions of digraphs; tournaments; every tournament has a king; Sec 5.3: walks and paths; equivalence relation; connected graphs; strongly connected and weakly connected digraphs 5. Jan 16, Wed. cut vertices and cut edges; use of maximal paths; König thm characterizing bipartite graphs; Königsberg bridge problem; eulerian circuits; 6. Jan 18, Fri. proof of characterization of eulerian graphs; decompositions into cycles; drawing graphs with minimum strokes; Chinese Postman Problem; Sec 5.4: trees; basic properties; characterizations Jan 21, Mon. Martin Luther King Day, no class. 7. Jan 23, Wed. more basic properties of trees; spanning trees; edge exchange property; minimum weight spanning trees; Prim and Kruskal algorithms; proof of correctness of Kruskal algorithm 8. Jan 25, Fri. Sec 15.2: counting spanning trees; edge contraction; recurrence; Matrix Tree thm; inductive proof; Sec 1.3: Cayley's formula for the number of labeled trees; proof 9. Jan 28, Mon. Sec 5.4: distance and related definitions; center of a tree; Sec 6.1: bipartite matching and systems of distinct representatives; Hall theorem with induction proof; marriage theorem 10. Jan 31, Wed. Ore defect formula; vertex covers; König-Egerváry thm; relations among independence number, matching number, vertex covers, and edge covers; Gallai theorem 11. Feb 1, Fri. Sec 6.3: algorithmic issues; symmetric difference of matchings; M-augmenting paths; maximum weighted bipartite matching 12. Feb 4, Mon. Sec 6.2: Tutte's 1-factor thm; deficiency; Berge-Tutte formula; proof 13. Feb 6, Wed. Petersen's thm on 1-factors in cubic graphs with no cut-edge; Plesnik generalization; Petersen's 2-factor thm; f-factors; transformation showing equivalent to 1-factors Sec 7.1: separating sets, k-connected, connectivity; examples, including complete graph; minimum degree bound; minimum number of edges in a k-connected graph on n vertices 14. Feb 8, Fri. Harary graph; connectivity of hypercube; vertex k-splits; disconnecting sets, k-edge-connected, and edge connectivity; edge connectivity of complete graphs; edge cuts; minimum degree bound; Whitney thm 15. Feb 11, Mon. size of disconnected piece when kappa'