#
Math 412

Introduction to Graph Theory

Sections X13 and X14

**Instructor:** Alexandr Kostochka

**Office:** 234 Illini Hall

**Phone:** (217) 265-8037 (office)

**Fax:** (217) 333-9576

**E-mail:**
kostochk@math.uiuc.edu

**Time and place:** 12 Noon - 12:50 am MWF, 245 Altgeld Hall

**Final exam:**
1:30-4:30 p.m., Friday, December 14.

**Office hours:** 3-4 pm MWF and by
appointment

##
Class Announcements

There will be no classes on Wednesday, September 26 and Friday, September 28 (the classes will
be compensated by the evening exams). So, the due date for HW4 is Wednesday, October 3.

Recall that we have Test 1 on Wednesday, October 03 from 7pm to 8:30pm.
Topics covered by the test are below.
Note that the items 13-15 (below the dotted line) are only for definitions and statements.
1. Definitions. Walks, trails, paths, cycles, closed walks.
2. Graph of the unit cube, Petersen's Graph and de Bruijn Graph.
3. Bipartite graphs. Konig's Theorem - a characterization of bipartite graphs.
4. Isomorphism of graphs.
5. Representations of graphs: adjacency and incidence matrices.
6. Eulerian circuits and trails. Euler's Theorem.
7. Degree Sum Formula.
8. Extremal problems on graphs. Mantel's Theorem.
9. Graphic sequences. A theorem on such sequences.
10. Directed graphs: degrees, connectivity, Eulerian circuits.
Degree Sum Formula for digraphs. Euler's Theorem for digraphs.
11. Tournaments, kings in tournaments.
12. Trees, characterizations of trees.

- - - - - - - - - - - - - - - - - - - -

13. Distances in graphs. Radius, diameter and center of a graph.
Centers of trees. Jordan's Theorem.
14. Prufer codes. Cayley Formula.
15. Counting spanning trees in graphs, Matrix Tree Theorem.

Graphs to remember:
a) Complete and complete bipartite graphs, b) The k-dimensional cube Q_k,
c) Petersen graph, d) de Bruijn graph.

To look at your grades, go to
``www.math.uiuc.edu'', then ``courses'', then ``scores reports''.

Last changed on September 19, 2018.