Cycles · Theory Problems
Lesson 2
Advanced Problems.
- (20 points) Let a graph \(G\) with \(v(G)=n>2\) satisfy two conditions.
- for every \(k\in\mathbb{N}\) with \(k<\frac{n-1}{2}\), the graph \(G\) contains fewer than \(k\) vertices of degree at most \(k\).
- if \(n\) is odd, then the graph \(G\) contains at most \(\frac{n-1}{2}\) vertices of degree at most \(\frac{n-1}{2}\).
Show that then \(G\) is Hamiltonian. - (20 points) Let \(G\) be a connected graph with minimum degree \(\delta(G)\ge 2\). Prove that \(G\) contains a simple path or a cycle of length at least \(\min\{2\delta(G), v(G)\}\).
Hint:
Take a longest simple path \(P\). Use that every neighbor of an endpoint of \(P\) must lie on \(P\). - (20 points) Let \(v(G)\ge 3\) and \(\kappa(G)\ge \alpha(G)\), where \(\kappa(\cdot)\) denotes vertex connectivity and \(\alpha(G)\) is the independence number. Prove that then \(G\) is Hamiltonian.
Hint:
Take a longest cycle \(C\) and a component \(W\) outside it. What can be said? - (20 points) Let two ordered sequences \(a_{1} \le a_{2} \le \cdots \le a_{n}\) and \(b_{1} \le b_{2} \le \cdots \le b_{n}\) be given. We say that the sequence \(\{a_{i}\}_{i\in[1..n]}\) majorizes the sequence \(\{b_{i}\}_{i\in[1..n]}\) if \(a_{i} \ge b_{i}\) for all \(i\in[1..n]\).
Let \(G\) be a graph on \(n\) vertices. The degree sequence of \(G\) is the ordered sequence of degrees of its vertices \[d_{1} \le d_{2} \le \cdots \le d_{n}.\] We say that the graph \(G\) majorizes the graph \(H\) if \(v(G)=v(H)\) and the degree sequence of \(G\) majorizes the degree sequence of \(H\). A sequence \(0 \le a_{1} \le a_{2} \le \cdots \le a_{n} \le n - 1\) is called Hamiltonian if every graph on \(n\) vertices whose degree sequence majorizes \(a_{1},…,a_{n}\) contains a Hamiltonian cycle.
Let \(0 \le a_{1} \le a_{2} \le \cdots \le a_{n} \le n-1\), where \(n\ge 3\). Show that the following two statements are equivalent.
- The sequence \(a_{1},…,a_{n}\) is Hamiltonian.
- For every \(s<\frac{n}{2}\) the condition \(a_{s} \le s\) implies \(a_{n-s}\ge n-s\).
- (20 points) Let \(D\) be a simple directed graph on \(n>1\) vertices, and let \(h(D)\) be the number of directed Hamiltonian paths in \(D\). Let \(\overline{D}\) be the directed complement of \(D\): it has the same vertices, and for \(u\neq v\) the arc \(u\to v\) is in \(\overline{D}\) if and only if \(u\to v\) is not in \(D\). Prove that \[h(D) \equiv h(\bar{D}) \pmod 2.\]
Hint:
Count permutations of the vertices and use inclusion–exclusion on the set of consecutive pairs that are required to be edges. - (20 points) Suppose a graph \(G\) has a spanning Eulerian subgraph, and let \(H\) be its line graph (the vertices of \(H\) correspond to the edges of \(G\), and two vertices of \(H\) are adjacent if and only if the corresponding edges of \(G\) are adjacent). Prove that \(H\) has a Hamiltonian cycle.
- (20 points) In a graph on \(n\) vertices with \(5n\) edges, assume there are no cycles of length less than \(5\). Prove that the graph contains \(5\) cycles that are pairwise vertex-disjoint.
Hint:
Prove that in a girth-\(\geq 5\) graph, a shortest cycle has no chords and outside vertices connect to it at most once. - (20 points) In a graph on \(2021\) vertices, suppose there exists a Hamiltonian cycle and the graph contains no triangles. Prove that this graph has a vertex of degree at most \(808\).
- (20 points) Does there exist a \(2023\)-regular graph that has no spanning \(k\)-regular subgraph for any \(1 \le k \le 2022\)?
- (20 points) All simple cycles of a graph \(G\) have length divisible by an integer \(n \ge 3\). Prove that \(G\) has a vertex of degree at most \(2\).
Hint:
Consider a 2-connected block (biconnected component) that contains a cycle. Take a shortest simple cycle in that block and try to show that no vertex on it can have a neighbor outside the cycle, otherwise you can create a shorter cycle. Conclude that every cyclic block must actually be a simple cycle, and then use the block–cut tree to find a vertex of small degree.
Hint:
Assume a smallest counterexample with the maximum number of edges (so it behaves like a “closure”).
Hint:
One direction: assume a maximal non-Hamiltonian graph majorizing the sequence and use that it must be closed. Other direction: construct a counterexample.