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)