Instructor(s):

Gábor Wiener
Tamás Fleiner
Weeks
1-14
Contact hours
2x2 hours/week
Credit
4 credits

Short Description of the Course:
Graphs are fairly general structures that often come up naturally in everyday problems and, in particular, in problems of information technology.

Beyond traditional applications (like traffic or telecommunication networks), graph theory have recently became an indispensable tool in studying social networks (like Facebook), computer-based networks (like the internet graph or the webgraph), and other complex systems. The best strategy for developing an ability to recognize and handle those problems where a graph theoretical framework is useful is to study graph theory for its own sake. This course offers a fast introduction to the basic concepts of graph theory as well as a more detailed discussion of some of its classical topics.

Aim of the Course:
The objective of this course is to introduce students to some of the most important notions of graph theory and develop their skill in solving basic exercises. Students should also become able to identify graph theory problems in a natural way even when they appear in a different setting.

Prerequisites:
No prior knowledge of graph theory is needed, but some basic mathematical maturity is expected. That is, students taking the course should be familiar with basic proof techniques, such as mathematical induction, proof by contradiction, etc. and should be accustomed to developing their own proofs as homework exercises.

Detailed Program and Class Schedule:

  1. Introduction

    • Basic notions [Diestel 1.1, 1.2: page 5, 1.3: pages 6-8, 1.4: pages 10-12]
    • Trees and forests [Diestel 1.5: pages 13-14]
  2. Euler tours
    • The bridges of Königsberg
    • Euler tours and trails, Euler’s theorem [Diestel 1.8]
  3. Hamilton cycles
    • Hamilton cycles and paths
    • Necessary and sufficient conditions [Diestel 10.1: pages 293-294]
  4. Planarity
    • Plane and planar graphs [Diestel: page 47]
    • Stereographic projection
    • Euler’s formula [Diestel 4.2: page 95]
    • Minors, theorems of Kuratowski and Wagner [Diestel 1.7: page 19, Thm. 4.4.6]
  5. Planarity and duality
    • Dual of a plane graph [Diestel 4.6: pages 107-108]
    • Problems with the dual, polyhedra
  6. Graph coloring
    • Coloring vertices, greedy algorithm, Brooks’ theorem [Diestel 5.2: pages 120-121]
    • Lower bounds, Mycielski’s construction
    • Coloring edges, Kőnig’s theorem, Vizing’s theorem [Diestel 5.3: page 125]
  7. Midterm exam
  8. Coloring planar graphs, perfectness
    • 4-color theorem and 5-color theorem [Diestel 5.1]
    • Perfect graphs [Diestel 5.5: page 132], examples
    • Odd holes, odd antiholes and their relevance
    • Lovász’s theorem, strong perfect graph theorem [Diestel 5.5: pages 134-135]
  9. Matchings
    • Bipartite matchings, Kőnig’s theorem, Hall’s marriage theorem  [Diestel 2.1: pages 36-38]
    • Tutte’s theorem [Diestel 2.2: pages 41-43]
    • Gallai’s theorems
  10. Extremal graph theory
    • Mantel’s theorem
    • Turán’s theorem [Diestel 7.1: pages 171-173]
  11. Ramsey theory
    • Ramsey’s theorem [Diestel 9.1: page 270]
    • Ramsey numbers, upper and lower bounds [Diestel Thm. 11.1.3]
  12. Higher connectivity of graphs
    • Higher vertex- and edge-connectivity [Diestel 1.4: pages 11-12]
    • Menger’s theorems [Diestel Thm. 3.3.1, Thm. 3.3.6]
  13. Final exam

Method of Instruction:
Each class consists of two parts. In the first part some new theoretical issues are discussed while the second part is dedicated to problem solving. Discussion of the new topic is often interactive: students are encouraged to find algorithms, theorems, or the appropriate definition for a concept. In the second part of the class students work on problems of three different levels. Level 1 requires only the understanding of the basic concepts, theorems, and algorithms and the ability to apply them. Level 2 requires a deeper insight to the topic, while level 3 also requires original ideas. At the end of weeks students are given a problem of each level as a homework to be handed in next week (some level 3 problems worth extra credit, see Grading).

Grading:
The final grade is made of four components. 100 points can be given for work in class during the discussion of the new material and common problem solving. 300 points can be given for the homeworks (there are 25 homework problems of 12 points each and it is possible to earn extra points by solving some of the 5 optional level 3 problems). 300 points can be given for the midterm exam and also for the final exam. Both the midterm and the final exams contain theoretical questions as well as problem solving. A sample midterm exam can be found here, a sample final exam can be found here. Since most problems are more difficult than it is usual in undergraduate courses, cutoffs for letter grades are not at the usual percentages:

Points Grades
880-1000 A+
800-879 A
760-799 A-
720-759 B+
640-719 B
600-639 B-
560-599 C+
480-559 C
440-479 C-
400-439 D+
320-399 D

Textbook:
Students use their own notes taken in class. Supplementary textbook:
R. Diestel, Graph Theory, free online edition: diestel-graph-theory.com/basic.html. We refer to this online edition in the Detailed Program above.

Additional useful reading:
M. Aigner, G. Ziegler, Proofs from the Book, Springer-Verlag, Heidelberg, 1998.

Instructors' bio:

Gábor Wiener (born 1973) is an associate professor at the Department of Computer Science and Information Theory, Budapest University of Technology and Economics. He received his M.Sc. in mathematics (1996) and his Ph.D. in computer science (2003) from Eötvös University under the supervision of Gyula O. H. Katona. He got a NOKIA telecommunications research scholarship (1999), a young researcher scholarship at the Rényi Institute of Mathematics of the Hungarian Academy of Sciences (1999-2002) and a Suzuki Fellowship (2009). He was awarded the Farkas Gyula prize of the Bolyai János Mathematical Society (2003) and the “Excellent Teacher of the Department” prize (2005). His fields of research are search theory, graph theory and hypergraphs. He has been teaching combinatorics, graph theory, and computer science since 1996. His Erdős number is 3.

Tamás Fleiner (1971) is an associate professor of the Department of Computer Science and Information Theory, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics (BME). He received his Mathematics degree in 1995 at the Eötvös Loránd University in Budapest and he got his PhD in 2000 at the TU/e in Eindhoven. His main research areas are Combinatorial Optimization, Combinatorics and its connection with Game Theory. At the BME and ELTE, he teaches inroduductory courses to Computer Science and Game Theory.