Lesson 1

Basic Problems.

1. (10 points) Let a graph \(G\) be Hamiltonian. Show that for any non-empty set \(S\subseteq V(G)\) the inequality \(c(G-S)\le |S|\) holds, where \(c(\cdot)\) denotes the number of connected components.
2. (10 points) Prove that any tournament has a vertex \(u\) with the following property: for any other vertex \(v\), there is a directed path from \(u\) to \(v\) of length at most \(2\).
   Hint:

   Choose \(u\) with maximum out-degree.
3. (10 points) Prove that in any connected graph, there is a route that passes along each edge at least once and at most twice.
4. (10 points) A complement \(\overline{G}\) of a graph \(G\) is a graph on the same vertex set in which two vertices are adjacent if and only if they are not adjacent in \(G\). Prove that \(G\) or \(\overline{G}\) is connected.
5. (10 points) Is it true that:
   • every simple Eulerian graph has an even number of edges;
   
   
   • every simple Eulerian graph with an even number of vertices has an even number of edges;
   
   
   • every Eulerian bipartite graph has an even number of edges?
   
   

   Hint:

   For the first two, test very small Eulerian graphs (e.g., cycles) and then try “gluing” Eulerian pieces at a vertex. For the bipartite case, count \(|E|\).
6. (10 points) What is the minimum length of a string containing all binary strings of length \(n\) as substrings?
7. (10 points) Consider a connected simple regular graph \(G\) of degree \(4\). Prove that its edges can be colored red and blue so that every vertex is incident to exactly two red and exactly two blue edges.
   Hint:

   Use that a \(4\)-regular connected graph is Eulerian.
8. (15 points) Let a graph \(G\) contain a vertex \(x\) of odd degree. Prove that among the edges incident to \(x\), there is an edge \(e\) for which the number of different cycles passing through \(e\) is even.
   Hint:

   For each edge \(e\) incident to \(x\), let \(c(e)\) be the number of (simple) cycles containing \(e\). What can be said about sum of \(c(e)\) over all edges incident to \(x\)?
9. (15 points) Count the number of Hamiltonian cycles in the complete bipartite graph \(K_{n,n}\) for \(n>1\).
10. (15 points) Show that for any connected graph \(G\) with \(v(G)\ge 3\) and for any edge \(e\in E(G)\), the graph \(G^{3}\) contains a Hamiltonian cycle that includes the edge \(e\), where \(G^{3}\) is a graph on the same set of vertices, in which two vertices are adjacent if and only if there is a path between them in \(G\) of length at most \(3\).
11. (15 points) Suppose that in a connected graph \(G\) exactly \(2k\) vertices have odd degree. Prove that the edges of this graph can be covered by \(k\) paths with pairwise disjoint edge sets.