You need to register on Neptun for the exam day.

The description of the topics may seem complicated. However, I am interested in whether you are familiar with basic concepts and theorems. Clear speech and precise expression are a big plus. We delve into proofs only if someone requests a better grade. An example always makes a concept or definition more understandable.

1. • Define a graph degree sequence, the realizability of a sequence. State the Havel-Hakimi theorem and prove it. When can a sequence of natural numbers be realized by a simple graph? Provide an algorithm as your answer.
   • Define the concept of a map. Describe the map coloring problem. State the four-color theorem. Give the edge coloring version of the theorem. Prove that it is equivalent to the four-color theorem.
2. • Define a graph degree sequence, the realizability of a sequence. When can a sequence be realized by a tree? Prove it. Given a vertex set, assign a natural number to each element so that the assigned numbers form a sequence that can be realized by a tree. How many realizing trees exist? How many trees are there on a given vertex set? Justify your statements.
   • Define the concept of an intersecting set system. What is the edge number of an intersecting set system over an n-element set? Justify your answer. What about k-uniform set systems? State the Erdős-Ko-Rado theorem and outline its proof.
3. • State Cayley's theorem. Provide a bijective proof.
   • Define the concept of a Sperner system. Give examples of Sperner systems. State Sperner's theorem. Define the f-vector of a set system. Prove Sperner's theorem.
4. • Define an acyclic graph and the vertex-edge incidence matrix of an acyclic directed graph. How can you obtain the vertex-edge incidence matrix of a directed graph from its acyclic orientation? Describe which (|V|-1)x(|V|-1) submatrices of the vertex-edge incidence matrix of a acyclic G are full rank. Write down Kirchhoff's formula.
   • Define the concept of a homogeneous set. Explain the coloring language of the Ramsey topic. Define Ramsey numbers. Define Ramsey numbers for multiple colors and for k's. Provide an algorithm that computes a large homogeneous set in the case of multiple colors. What estimate can be given for Ramsey numbers?
5. • What do we mean by a matching in a graph? What optimization problem is related to the concept of matching? Describe the greedy algorithm that finds a large matching. What can be said about the size of the output? Justify it.
   • State Wagner's theorem. At the beginning of the indirect proof, we took a minimal counterexample. What can we say about this counterexample? Given a graph-theoretical circuit and subsets of its vertices colored red and blue (not necessarily disjoint). Define when we can call the two color sets separable. State the description equivalent to the definition given in the lecture.
6. • What do we mean by a matching in a graph? What optimization problem is related to the concept of matching? Define the concept of an augmenting path (for a matching). How can we search for augmenting paths in a bipartite graph?
   • Define the parameters of an incidence of a point and a line in a geometric system. State the Szemerédi-Trotter theorem. Prove the theorem. Provide a precise description of the auxiliary tools/theorems used (proofs are not required).
7. • What do we mean by a matching in a graph? What optimization problem is associated with the concept of matching? Let G be a balanced, simple bipartite graph, and let B be its bipartite adjacency matrix. What can we infer if the determinant of B is not 0? Provide a randomized algorithm that tests for the existence of a perfect matching in balanced bipartite graphs. State the Schwartz lemma. What is the connection between the lemma and the algorithm?
   • How did we define k-edge-connected graphs? Define the boundary of a vertex set. Define k-edge-connected graphs based on the boundary concept. When do we say that a graph is minimally k-edge-connected? State Mader's theorem. State the submodular inequality. Prove it.
8. • What do we mean by a matching in a graph? What optimization problem is related to the concept of matching? What do we mean by a vertex cover/dominating set in a graph? What optimization problem is related to the concept of vertex cover/dominating set? Given a matching M and a vertex cover/dominating set L. Under what circumstances can we be sure that M is an optimal matching? Prove that the path augmentation search presented in the lecture is complete for bipartite graphs.
   • Define the crossing number of a graph. What are the crossing numbers of K₃, K₄, K₅, K_2,3, and K_3,3? Prove that |E|-3|V| is a lower bound for the crossing number. State the crossing lemma. Prove it.
9. • What do we mean by a matching in a graph? What optimization problem is related to the concept of matching? Define the concept of an augmenting path (for a matching). How did we search for augmenting paths in a graph (Edmonds)?
   • Define the subgraph, topological subgraph, and minor of a graph. What can be said about these "parts" when examining them in the context of planar graphs? Provide examples of non-planar graphs. State Kuratowski's theorem. State Wagner's theorem.
10. • What do we mean by a matching in a graph? What optimization problem is related to the concept of matching? Define the concept of an augmenting path (for a matching). What do we mean by a Tutte obstacle? Let M be a matching and T a Tutte obstacle. Under what circumstances can we be sure that M is an optimal matching? Prove that if Edmonds' path augmentation search fails, then the current matching is maximum.
    • What do we mean by a nice drawing in a graph? Define the domain and the boundary of a domain in the case of a nicely drawn graph. Define the dual of a nicely drawn graph. Provide connections between the parameters of the original and dual graph.
11. • What do we mean by a matching in a graph? What optimization problem is related to the concept of matching? Define the concept of an augmenting path (for a matching). What do we mean by a Tutte obstacle? Let M be a matching and T a Tutte obstacle. Under what circumstances can we be sure that M is an optimal matching? Prove that if Edmonds' path augmentation search fails, then the current matching is maximum.
    • Define the function ext(n;T). Estimate the function's value from below and above if T has 1 or two edges. Prove that if the forbidden T graph is a tree, then ext(n;T) can be upper-bounded by a linear function of n.
12. • What do we mean by a good coloring in a graph? What optimization problem is related to the concept of coloring? State Hajós' theorem. Split the theorem into two implications. Which one is simpler? Justify it.
    • Define the ext(n;T) function. Provide upper bounds for the ext(n;C₄) function. Describe the order of magnitude of its upper bound.
13. • What do we mean by a legal coloring in a graph? What optimization problem is related to the concept of coloring? Define the concept of the girth of a graph. State Erdős' theorem on the above concepts. Prove it.
    • Define the function ext(n;T). Provide upper bounds for the ext(n;C₄) function. Describe the order of magnitude of its upper bound.
14. • Define the concept of a legal/good edge coloring in a graph. What optimization problem is related to the concept of edge coloring? State Shannon's and Vizing's theorems. Prove one of them.
    • Define the concept of a homogeneous set. Explain the coloring language of the Ramsey topic. Define Ramsey numbers. Define Ramsey numbers for multiple colors and for k's. Provide an application of the Ramsey theorem.