Graph Theory

A tantárgy neve magyarul / Name of the subject in Hungarian: Gráfelmélet

Last updated: 2010. november 11.

Budapest University of Technology and Economics
Faculty of Electrical Engineering and Informatics

Mérnök informatikus szak

BSc képzés

Course ID Semester Assessment Credit Tantárgyfélév
VISZA086   3/1/0/v 4  
3. Course coordinator and department Dr. Fleiner Tamás,
Web page of the course
4. Instructors










Department of Computer Science and Information Theory




Assoc. professor


Department of Computer Science and Information Theory




Assoc. professor


Department of Computer Science and Information Theory




Assoc. professor


Department of Computer Science and Information Theory




Assistant lecturer


Department of Computer Science and Information Theory


7. Objectives, learning outcomes and obtained knowledge

The objective of the first part of this course is to introduce the students with some of the most important notions of graph theory and develop their skill to solve basic exercises. It is also an objective of the course that on the way they become able to identify graph theory problems in a natural way even if those appear in a different setting.



The objective of the second part is to deepen the students' knowledge of graph theory by showing interrelations of some of the seemingly loosely related concepts and further develop their problem solving skills. Although there is no formal prerequisite for this course, some basic mathematical maturity is expected. 


8. Synopsis
  1. Introduction


    Basic notions of graphs


    Why are they interesting and what are we interested in about them


    Trees and their main properties


    Coding and counting trees on n labelled vertices


2. The Königsberg bridges problem and Euler tours


          Euler tours in directed graphs


          The existence of deBruijn sequences


          Hamiltonian cycles


          The different nature of Hamiltonian cycles and Euler tours


          Necessary conditions for Hamiltonicity


          Sufficient conditions for Hamiltonicity due to Dirac, Pósa, Ore, and Chvátal


  1. Matchings and their relevance


          Necessary and sufficient conditions for the existence of a perfect matching in   bipartite graphs


          Kőnig's min-max theorem


          Perfect matchings in general graphs, Tutte's criterion


          Stable matchings and their use


    The existence of stable matchings in bipartite graphs


  1. Network flows


          The augmenting paths algorithm


          The Ford-Fulkerson min-max result and its relation to Kőnig's one


          Menger's min-max results


          The relevance of min-max formulae in general


  1. Planarity,


          Euler's formula and Kuratowski's criterion


          Minors and Wagner's criterion


          The equivalence of forbidding the Kuratowski graphs as minors and as topological    




  1. Coloring graphs as a model for scheduling


           Bounding the chromatic number from above, greedy algorithm


           Bounding the chromatic number from below, Mycielski's construction


           Coloring edges


     Line graphs and the analogs of the previous bounds


     Improving the greedy algorithm, Vizing's upper bound


  1. Coloring planar graphs, 4-color theorem and 5-color theorem,


    Tait's result on the the relation of edge-coloring cubic planar graphs and the 4-color     




    Perfect graphs, perfectness of bipartite graphs, their line graphs and the complements


    of these


    Odd holes, odd antiholes and their relevance


    Relation of complementation and perfectness in general


8. List coloring


    Relation of the list coloring number to the chromatic number, list coloring conjecture


    Galvin's theorem and its relation to stable matchings


          List coloring planar graphs


    Thomassen's inductive argument


    Voigt's construction for the sharpness of Thomassen's result


  1. Extremal graph theory


          Turán's sharp upper bound on the number of edges if the clique number is bounded


    The Erdős-Stone theorem and the Erdős-Simonovits limit result


          The Kővari-T.Sós-Turán upper bound for the analogous bipartite problem


  1. Ramsey theory


    Basic Ramsey-type results in graph theory


    Examples of Ramsey-type results outside graph theory


    Ramsey numbers, upper and lower bounds


  1. Hypergraphs as generalizations of graphs and as set systems


          Ramsey's result in the hypergraph setting


          Sperner systems and their maximum possible size


          LYM inequality


          Intersecting set systems, Erdős-Ko-Rado theorem


  1. Kneser's conjecture as a problem on hypergraphs


          Kneser graphs and their chromatic number, the Lovász-Kneser theorem


          Kneser graphs and fractional colorings


9. Method of instruction Lectures and recitations


10. Assessment The grade given will be based on four homework assignments consisting of five problems each, and on the final exam. The solutions should be handed in by the due date that will be on the 4th, 6th, 9th and 11th weeks, respectively. The assignments will be handed out at least a week before the due date. (Please note that no late homework will be accepted.) The assignments weigh 15% each while the final exam weighs 40% in calculating the final score.


12. Consultations You can reach the instructor at the following e-mail address for consultation:




13. References, textbooks and resources

Reinhard Diestel: Graph Theory, 3rd Edition, Springer-Verlag, Heidelberg, 2005;  or  


Béla Bollobás: Modern Graph Theory, Springer-Verlag, Heidelberg, Corr. 2nd printing 2002.


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


14. Required learning hours and assignment
Number of contact hours




Preparation to the classes




Preparation to the tests







Assigned reading



Preparation to the exam








15. Syllabus prepared by










Department of Computer Science and Information Theory