Graph Theory Problem Set

For math and applied math MSc, and PhD students

Spring 2026

Lecturer: Zoltán Király

Wednesday, 16:00-17:30, 3.357.


Only for my students


Announcements


Lect 1 (FEB 11)

Exe 1: Can the following sequence be the degree sequence of
a) 3, 3, 3, 3, 5, 6, 6, 6, 6, 6, 6 -- a multigraph?
b) 3, 3, 3, 3, 3, 5, 6, 6, 6, 6, 6, 6 -- a bipartite multigraph?
c) 1, 1, 3, 3, 3, 3, 5, 6, 8, 9 -- a simple graph?
d) 2, 2, 2, 2, 2, 5, 6, 7, 8, 8, 8 -- a simple graph?

Exe 2: When is \(d_1\le d_2\le \ldots d_n\) a degree sequence of a tree?

Exe 3: When is \(d_1\le d_2\le \ldots d_n\) a degree sequence of a
a) multigraph?
b) loopless multigraph?
c) loopless connected multigraph?

Exe 4: When is \(a_1\le a_2\le \ldots a_n\) and \(b_1\le b_2\le \ldots b_m\) a degree sequence of a
a) bipartite multigraph?
b) connected bipartite multigraph?

A sequence is called graphical, if it is a degree sequence of a simple graph. Let \(d_1\le d_2\le \ldots d_n\) be a sequence. The algorithm of Havel and Hakimi is based on the following idea.
Thm: The sequence \(d_1\le d_2\le \ldots d_n\) is graphical iff the sequence \(d_2\le d_3\le\ldots\le d_{n-d_1}, d_{n-d_1+1}-1\le \ldots\le d_n-1\) is graphical.
Exe 5: Prove this theorem.

Hw 1: When is \(a_1\le a_2\le \ldots a_n\) and \(b_1\le b_2\le \ldots b_m\) a degree sequence of a simple bipartite graph?
Hw 2: When is \(d_1\le d_2\le \ldots d_n\) an out-degree sequence of a Tournament?
Hw 3: If in a directed graph G, the longest path has length m then G has a chromatic number at most m+1.


Lect 2 (Feb 18)

Discussion of the Homework (except Hw 3).

Exe 1 (Orientation lemma): Given \(G\) and \(m: V\to \mathbb Z_0^+\). Is there an orientation of \(G\) with \(\delta(v)=m(v)\), and for all \(v\in V\)?
Notation: \(\delta(v)\) is the out-degree of \(v\), \(\varrho(v)\) is the in-degree of \(v\), and for \(X\subseteq V\) \(m(X)=\sum_{x\in X} m(x)\).
Prove that such an orientation exists iff \(m(V)=|E|\) and for all \(X\subseteq V\) we have \(m(X)\ge i(X)\), where \(i(X)\) denotes the number of edges induced by \(X\).

Exe 2: What is the condition to have a strongly connected orientation with the prescribed out-degrees?

\(G\) is a directed graph, \(c: E\to \mathbb Z\).
Definition: \(\pi: V\to \mathbb Z\) is an admissible potential if for each \(uv\in E\)   \(c(uv)\ge \pi(v)-\pi(u)\).
\(\pi: V\to \mathbb Z\) is an exact potential if for each \(uv\in E\)   \(c(uv)= \pi(v)-\pi(u)\).

Exe 3: a) There exists an admissible potential iff there are no negative cycles.
b) If \(G\) is strongly connected then there exists an exact potential iff every cycle has length 0.

Hw 4: \(G\) is a directed graph. For every undirected cycle \(C\), there are at least \(|C|/k\) edges going in both directions. Then \(G\) is \(k\)-colorable (if \(k>1\)).

Hw 5: If everybody knows exactly 4 other people then they can be seated around round tables such that everybody knows their two neighbors. (At least 3 people per table).

Hw 6: Prove the equivalence of Frobenius' theorem and the Orientation lemma.
Frobenius (1917): in a bipartite graph \(G=(U\cup V, E)\) there exists a perfect matching iff \(|U|=|V|\) and for all \(X\subseteq U\) we have \(|N(X)|\ge |X|\).


Lect 3 (FEB 25)

Discussion of the Homework (except Hw 6).
G is k-colorable iff there is an acyclic orientation where every path has length at most k-1.

Eulerian tours in undirected and directed graphs.

G is a strong digraph and Eulerian (for every vertex its in-degree=out-degree). T is a spanning in-arborescence rooted at vertex s.
Algorithm: starting from s, at a vertex v we choose an outgoing edge not used before. Further rule: from a vertex v, we may use the outgoing arborescence edge iff we already used all the other edges.
Claim: this gives an Eulerian walk.

Edge-coloring theorem of Kġnig.

Hw 7: G is a directed graph having a vertex with out-degree at least 3. Then the number of Eulerian tours is even.
Hw 8: We define graphs \(G(k,n)\) as follows. The vertices are vectors of length k with coordinates integers between 1 and n. There is a directed edge from vertex \((a_1,a_2,...,a_k)\) to vertex \((a_2,...,a_k,b)\) for every b.
Part a) \(G(k,n)\) is Eulerian, and has an Eulerian tour.
Part b) \(G(k,n)\) is Hamiltonian.
Hw 9: G is a digraph. Prove that the number of Eulerian tours is divisible by the product of numbers \((\delta(v)-1)!\).
Hw 10: G is 3-regular. Prove that G has a 'proper' orientation iff it is bipartite. Here an orientation is proper iff every in-degree is at most 2 and connected vertices have different in-degrees.
Hw 11: Part a) We have an \(n\times n\) Latin square. The first k rows are filled properly. Prove that we can finish the filling.
Part b) Now the upper left \(k\times \ell\) rectangle are filled properly. Under what conditions can the filling be finished?
Part c) M is a non-negative \(n\times n\) matrix where every row sum and every column sum is n. Prove that we can write \(M(i,j)\) integers between 1 and \(n\) into every cell \((i,j)\) such that every row and every column contains every numbers between 1 and \(n\).


Lect 4 (MAR 4)

Discussion of the Homework.

Extra homework for extra points: give a direct proof for the fact that in a strong directed Euler graph the number of spanning in-arborescences rooted in \(s\) is the same as the number of spanning in-arborescences rooted in \(t\).

Proof for Kġnigs edge-coloring theorem.

Traveling through a maze.

Hw 12: The edges of \(G\) are partitioned into classes \(E_1\ldots E_k\). Prove that G has a smooth orientation (for every vertex the difference between in-degree and out-degree is at most 1), which induces a smooth orientation on every \(G_i\).
Hint: (if you are going to use it, you must prove it) \(G\) is Eulerian, at every vertex the incident edges are divided into pairs. Then there exists an Eulerian orientation in which at every vertex every pair is well-oriented: one edge is oriented toward \(v\), and the other edge of the pair is oriented from \(v\).
Hw 13: \(G\) is a connected multigraph with \(n\) vertices and \(m\) edges. Then the number of cycles is at most \(2^{m-n+1}-1\).
Hw 14: When can we write numbers \(+1\) or \(-1\) at every edge in a connected graph \(G\), such that at every vertex the absolute value of the sum on the incident edges is at most 1?
Hw 15: Part a). In hockey usually the winner gets 3 points but if it wins in overtime then it gets 2 points and the other team gets 1 point. When can a given score sequence be the result of a tournament?
Part b). Tournament in card game `ulti': every triple \(n\choose 3\) plays a party, and in each party the unique winner gets 1 point. When can a given sequence be the score vector?
Hw 16: When a mixed graph G does have an Eulerian orientation?


Lect 5 (MAR 11)

Discussion of the Homework.

Orientation lemma for hypergraphs.

OPEN PROBLEM: When can \(d_1\ldots d_n\) be the result of a football tournament?

\(T\)-joins and \(T\)-odd orientations.

OPEN PROBLEM: Give a necessary and sufficient condition for a graph having a \(T\)-odd strong orientation?

OPEN PROBLEM: Give a necessary and sufficient condition for a graph having a \(T\)-odd acyclic orientation?

Ear-decompositions.

Block decompositions, end-block.

Hw 17: \(G\) is 2-connected, \(x\) is an arbitrary vertex. Then there are at least 2 neighbors \(y\) such that \(G-x-y\) is connected. (Alternatively, \(G/xy\) is 2-connected.)
Hw 18: \(G\) is 2 edge-connected -> there exists a strong smooth orientation.
Hw 19: \(G\) is 2-connected, \(s\) and \(t\) are vertices. Prove that it is possible to acyclically orient \(G\) such that all edges are on a directed \(s\leadsto t\) path.
Hw 20: a) If \(G\) is 2 edge-connected, \(e\) and \(f\) is a cutting edge pair, \(f\) and \(g\) is a cutting edge pair, then \(e\) and \(g\) is also a cutting edge pair.
b) \(G\) is 2 edge-connected, \(e\sim f\) if \(e=f\), or if \(e\) and \(f\) is a cutting edge pair. What characterizes the equivalence class of a given edge \(e\)?
Hw 21: \(G\) is 2-connected, \(T\) is a vertex set, \(0\lt k\lt |T|\). Then there is a partition \(V=X\cup Y\) such that \(G[X]\) and \(G[Y]\) are connected and \(|X\cap T|=k\).

Extra credit assignments, first round. Deadline is April 15, 4 pm. Each exercise must be submitted after a \newpage but altogether in 1 pdf. Unless otherwise indicated, a good solution submitted is worth 2 points. The exercises.


Lect 6 (MAR 18)

Discussion of the Homework.

Frobenius --> Hall --> Ore.
Gallai's identities.

Tutte's theorem, deficiency, barrier, factor-critical graphs.
Def: A barrier \(X\) is strong if every odd component of \(G-X\) is factor-critical.

Hw 22: \(G\) is a connected graph. When do we have an acyclic orientation, where there is exactly one source and exactly one sink?
Hw 23: Prove that \(2 \nu(G) = n - def(G)\), where \(\nu(G)\) is the size of a maximum matching. ( Only Tutte's theorem can be used).
Hw 24: \(X\) is a given set of vertices. When we have a matching covering \(X\)? ( Only Tutte's theorem can be used).
Hw 25: \(G\) is a 3-regular 2 edge-connected graph. Then \(G\) has a perfect matching.


Lect 7 (MAR 25)

Discussion of the Homework.

For each barrier there is a strong barrier containing it.
Tutte's theorem remains true with \(q'\) which counts the factor-critical components.

Graph \(F\) is factor-critical iff its blocks are factor-critical.

Which bipartite graphs are factor-critical? Prove Frobenius from Tutte.

If barrier \(B\) contains strong barrier \(A\), then \(B\) can intersect only the even components of \(G-A\).

Hw 26: A connected graph \(F\) is factor-critical iff the empty set is the unique barrier.
Hw 27: \(G\) is connected. Define \(A\) as the intersection of all strong barriers. Let \(D\) be the union of odd components of \(G-A\) and \(C\) be the union of even components of \(G-A\). Prove as much interesting statements about these sets as you can. (You may use ECA 13).
Hw 28: \(G\) is 2-connected and \(2d\)-regular. The edge set can be decomposed into two \(d\)-regular graphs iff \(nd\) is even. Moreover, the edge set can always be decomposed into \(d\) 2-regular graphs.


Lect 8 (APR 8)

Discussion of the Homework.

Dulmage-Mendelsohn.

Planar graphs, duality, the connection of spanning trees with the spanning trees of the dual. Euler's formula.


Lect 9 (APR 15)

Discussion of the following ECAs: 12 and 8.

Maximum number of edges in planar graphs.

When can be the faces of a planar graph colored by two colors?

Extra credit assignments, second round. Deadline is May 6, 4 pm. Each exercise must be submitted after a \newpage but altogether in 1 pdf. Unless otherwise indicated, a good solution submitted is worth 2 points.
The exercises.

Hw 29: \(G\) is planar, Hamiltonian. Then, its countries can be colored using four colors. (Of course, the four-color theorem cannot be used!)
Hw 30: \(G\) is a planar graph where each face is a hexagon (including the outer face). Does it follow that \(G\) has a perfect matching?
Hw 31: If the outer face of a planar graph is a pentagon and all other faces are triangles, then it cannot be Eulerian.
Hw 32: \(G\) is a planar, strongly connected directed graph. Prove that there is a face with left orientation, and there is another face with right orientation.


Lect 10 (APR 22)

Discussion of the Homework.

Alternating orientation of the edges of a 4-regular planar graph.
Five-color theorem (with two proofs).
Four-color theorem in the case the maximum degree is 5 but the graph is not 5-regular.
Fault-finding in a wrong proof for four-color theorem (Kempe, 1879).

\(G\) is a 3-regular 2-connected planar graph. Its faces can be colored using four colors iff its edges are 3-colorable (Tait, 1880).

Hw 33: In a simple 4-regular planar graph, when does a two-coloring of the edges exist which alternates at all the vertices? (At every vertex the four incident edges should be red-blue-red-blue.)
Hw 34: There are some lines on the plane such that at most 2 lines pass through any point. The vertices of a planar graph are the intersection points, and two vertices are adjacent if the corresponding segment does not contain any other vertex. Prove that this graph can be colored using 3 colors.
Hw 35: A triangulated planar graph is 3-colorable iff it is Eulerian.
Hw 36: For which values of \(n\) does a connected simple 4-regular planar graph on \(n\) vertices exist?


Lect 11 (APR 29)

Discussion of the Homework.

If the faces of a 2 edge-connected planar graph can always be colored using four colors (this is the four-color theorem), then the faces and vertices can be colored at the same time by four colors (adjacent vertices can have the same color, but adjacent faces cannot, and an adjacent vertex-face pair neither can have the same color).
\(G\) is a 3-regular 2-connected planar graph. Its faces can be colored using four colors iff the vertices can be labeled with \(+1\) or \(-1\) such that the sum on every face is divisible by 3.
The vertices of a simple planar graph can be colored using two colors such that no country is monochromatic.

List-coloring: \(G\) is connected, lists of colors at every vertex, \(|L(v)|\ge d(v)\) for all \(v\in V\).
a) \(\exists v\in V : |L(v)|> d(v)\). Then \(G\) is \(L\)-colorable.
b) \(G\) is 2-connected, \(\exists a,b\in V : L(a) \ne L(b)\). Then \(G\) is \(L\)-colorable.
c) \(G\) is 3-connected, \(|L(v)|\ge \Delta\), \(\Delta>2\). If \(G\) is not a clique, then \(G\) is \(L\)-colorable.
Extra homework for extra points: c) remains true when \(G\) is only 2-connected or only connected.

Deadline for second series of ECA.

P>


Lect 12 (MAY 6)

The proof for part c).

Discussion of the following ECAs: 10, 14, 15 d), 17, 18.


Lect 13 (MAY 13) 16:00--18:00

Midterm exam.

Main rules: no digital tool (tablet, phone, etc.) can be used. A good solution for any exercise is worths 1 point.