Lesson 2

Advanced Problems.

1. (20 points) Given natural numbers \(k, d, t\) such that \(k \ge 2\) and \(t < d\). It is known that in a graph, the degrees of all vertices are at least \(d\) and at most \(kd\). Prove that it is possible to remove several edges such that the degrees of all vertices in the resulting graph are at least \(t\) and at most \(kt\).
2. (20 points) In a tripartite graph where each part contains \(n\) vertices, every vertex is adjacent to at least \(\frac{3n}{4}\) vertices in each of the two other parts. Prove that this graph can be decomposed into \(n\) disjoint triangles.
3. (20 points) In a bipartite graph \(G = (V_{1}, V_{2}, E)\), both parts are countable, and the degree of every vertex is finite. For any subset of vertices \(A \subseteq V_{1}\), the condition \(|N_{G}(A)| \geq |A|\) holds. Prove that there exists a matching covering the entire part \(V_{1}\).
4. (20 points) A holey triangle is an upward equilateral triangle of side length \(n\) with \(n\) upward unit triangular holes cut (in standard lattice positions). A diamond is a \(60^{\circ}\)–\(120^{\circ}\) unit rhombus (two adjacent unit triangles). Prove that a holey triangle \(T\) can be tiled with diamonds if and only if the following condition holds: every upward equilateral triangle of side length \(k\) in \(T\) contains at most \(k\) holes, for \(1\le k\le n\).

   An example of a holey triangle is shown on the left, while on the right a possible tiling is shown.

   

5. (20 points) The vertices of a graph \(G\) have degree at most \(2000\). Prove that it is possible to color the halves of edges of \(G\) in colors \(1,2,…,2000\) so that the two halves of each edge are colored with difference \(1\), and all halves of edges sharing a common vertex have different colors.
6. (25 points) For an arbitrary graph \(G\), denote by \(o(G)\) the number of connected components with odd number of vertices of \(G\), that is, components containing an odd number of vertices. Prove that a graph \(G\) has a perfect matching if and only if for every \(S \subset V(G)\) the inequality \[o(G - S) \le |S|\] holds.
   • (5 points) Show the necessity condition.
   
   
   • (15 points) Let \(G\) be a graph with no perfect matching such that adding any new edge to \(G\) creates a perfect matching. Let \[U = \{ u \in V(G) : \operatorname{deg}_{G}(u) = |V(G)| - 1 \}.\] Show that the graph \(G - U\) is a disjoint union of complete graphs.
   
   
   • (5 points) Finish the proof.
   
   

7. (25 points) A graph in which every vertex has degree \(3\) is called cubic. A bridge of a graph is an edge that does not belong to any cycle.
   • (15 points) Let \(G\) be a connected cubic graph with at most two bridges. Prove that \(G\) has a perfect matching.
   
   
   • (10 points) Give an example of a cubic graph with at most three bridges which has no perfect matching.