Inhaltsverzeichnis / Content

Graphentheorie

Wintersemester 2025/26
Stefan Felsner

Lecture 1, Tue. 14.10.2025

    3 trigger problems     
    Basics
          what is a graph?
          examples of graphs;
          Kneser graph K(7,3)
          Coxeter graph
          Why graph theory ?
        Solution of problem I
          iso- and other morphisms
          how many graphs?
      Solution of problem I
      

       Handshaking
       graph homomorphisms
       how many graphs?
    Solution of problem II
       Geometric graphs without disjoint edges
       Topological graphs, Thrackles

       Subgraphs, induced subgraphs, and minors 
    Solution of problem III
       Rigid grids: paralell classes of edges - connectivity of auxiliary graph
       Graph rigidity in the plane - Laman density condition    
    Degree sequences
       Charakterization of Havel and Hakimi

       The flip-graph of 2-switches
       Thm. of Erdös-Gallai
    Paths and cycles
       Distances
       Connectivity
         vertex- and edge-connectivity 

    Theorem of Menger
       proof of the u-v variant
       The classical Menger's Theorem
       8 variants of Menger's Theorem
         Ford-Fulkerson and König-Egervary
 

    Trees and Forests
       Characterizations of trees              
       Spanning trees
         2 algorithmic proofs for their existence
          a glimpse on matroid
          a glimpse on search trees [DFS/BFS]

     BridgeIt
        The game
        A winning strategy based on spanning trees
     Cayley' Theorem on the number of trees
        Proof 1. Prüfer; a bijection between trees and Prüfer codes
        Proof 2. Clarke; refined counting and recursio          
	Proof 3. Joyal; A bijection involving the cycle-forests of maps [n] to [n]

     Euler Cycles
        Königsberg Bride Problem
        Even Degree equivalent to Eulerian
     Hamiltonian Cycle
        Large Minimal Degree (Dirac´s Theorem)
        Theorem of Erdös-Chvatal

       The hamiltonian closure
       Hamiltonian cycles in squares and cubes of trees
    Gray-codes for combinatorial structures
       Combinatorial families 
       Hamiltonian cycles in flip graphs
       The classical Gray-code for 01-vectors

       Zig-zag permutation languages
         Algorithm J
         Instances of Alg J: permutations, Catalan, 01-vectors
     F2 vector spaces of graphs
           F2 orthogonality
           cut and cycle space
           fundamental bases of cut and cycle space

      Matrix-Tree Theorem
              Proof sketch with Cauchy-Binet
           Proof of the Matrix-Tree Theorem for digraphs
              arborescences
              reduction to digraphs with outdeg(v) = 1 for all v
      Eulerian paths and cycles
         Memory Wheels and de Bruijn graphs
         BEST Theorem
           Counting eulerian cycles in directed graphs

        The number of eulerian cycles in de Bruijn Graphs
           Eigenvalue version of the matrix tree theorem
           Path of length n in Bn(m)
           The eigenvalues of the Laplacian of Bn(m)

         Turán´s Theorem
            Proof 1: optimization - shifting weights
            Proof 2: short induction
            Proof 3: the 3 vertex property
            - characterizing maximizing examples
         Extremal functions ex(n,H)
         Theorems of Erdős-Stone and Erdős-Simonovitz

         Extremal functions for bipartite graphs
         ex(n,C4)
      An inequality for the independence number α (Wei Inequality)
         Turán as a consequence of Wei
         proof via random permutations
         proof: analyzing Algo MAX

   Ramsey Theory
        Monotone subsequences (Erdös Szekeres)
        Breaklines in domino tilings of the 6x6 board
        Theorems of Schur / van der Waerden / Ramsey
        (Ein Beitrag zu den Sätzen von Schur, Ramsey und Fermat: video)  
    Graph-Ramsey
        Existence of R(k,k) via induced colorings
        Existence of R(k,k) by induction, binomial coefficients
        Probabilistic lower bound
    The general set Ramsey numbers: Rk(t;n1,..,nt)

    Applications of Ramsey numbers: The Happy Ending Problem (convex subsets)
         Esther Klein Lemma
         Theorem of Erdős Szekeres
            N(n) < R4(5,n)
            N(n) < R3(n,n)
            k-caps and k-cups - the classical upper bound
         Dual ES: Pseudoline arrangements and signotopes

   Planar Graphs
        Drawings, crossings, the Jordan curve Theorem
         K5 and K3,3 are non-planar
         Dual Graphs
         Proofs of Euler´s formula
            dual trees

            induktion (Noah's arch)
            angle sums 
        Implications of Euler´s formula
        Coloring planar graphs with 6 colors
        Coloring planar graphs with 5 colors
            Kempe chains
       The "Art Gallery Problem"
       Straight line drawings of planar graphs (induction)

     Crossing numbers
        Simple drawings
        Lower bounds for crossing numbers
        The Crossing Lemma
             Unit distances - an application of the crossing lemma
             The chromatic number of the plane

        Hill's conjecture for cr(Kn) 
        Moon´s probabilistic drawings of Kn with few cross>
        Antipodal drawings of M2k, 
             i.e., K2k minus perfect matching