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

    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    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






    Gábor SIMONYI




    Department of Computer Science and Information Theory


    Tamás FLEINER


    Assoc. professor


    Department of Computer Science and Information Theory


    Dávid SZESZLÉR


    Assoc. professor


    Department of Computer Science and Information Theory


    Gábor WIENER


    Assoc. professor


    Department of Computer Science and Information Theory


    Ildikó SCHLOTTER


    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:


    Gábor SIMONYI:


    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






    Gábor SIMONYI




    Department of Computer Science and Information Theory