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.
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|\).
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\).
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?
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.
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.
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.
Dulmage-Mendelsohn.
Planar graphs, duality, the connection of spanning trees with the spanning trees of the dual. Euler's formula.
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.
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?
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>
Discussion of the following ECAs: 10, 14, 15 d), 17, 18.
Main rules: no digital tool (tablet, phone, etc.) can be used. A good solution for any exercise is worths 1 point.