Trees · Theory Problems
Lesson 1
Basic Problems.
- (5 points) Prove that in any simple graph there exist two vertices with the same degree.
- (5 points) Let \(G\) be a graph in which every vertex has degree at least \(2\). Prove that \(G\) contains a cycle.
Hint:
Start at any vertex and keep walking to a new neighbor; with finitely many vertices you must eventually repeat a vertex. - (5 points) A graph has \(100\) vertices and \(800\) edges.
- Prove that at least one vertex has degree at least \(16\).
- Is it possible that all vertices have degree exactly \(16\)?
- (5 points) Prove that in any tree with maximum vertex degree \(k\) there exist at least \(k\) leaves.
Hint:
Remove a vertex of degree \(k\). - (5 points) King Gwydon had \(5\) sons. Among his descendants, exactly \(100\) people had exactly \(3\) sons each, and every other descendant died childless. How many descendants did King Gwydon have in total?
Hint:
Model the family as a rooted tree: each descendant has exactly one parent. - (10 points) Prove that in any connected graph there exists a vertex whose deletion leaves the remaining graph connected.
- (10 points) There are \(2019\) towns. The capital has \(1015\) roads leaving it, the town Dalny has \(1\) road leaving it, and each of the remaining towns has exactly \(44\) roads leaving it. Prove that it is possible to travel by roads from the capital to Dalny.
- (10 points) In a certain country, there are \(100\) cities connected by roads in such a way that between any two cities there is exactly one way to travel without turning back. Prove that one can start in some city, visit all cities, and return to the start while traveling along at most \(198\) roads.
Hint:
The condition means the road network is a tree. How many edges does it have, and how can you traverse a tree and come back? - (10 points) Does there exist a convex polyhedron with \(15\) faces such that every face is a triangle?
- (15 points) Let \(G\) be a connected weighted graph with all edge weights distinct. Prove that \(G\) has exactly one minimum spanning tree.
- (15 points) Let \(T\) be a tree with no vertices of degree \(2\). Prove that the number of leaves is more than half of the total number of vertices.
- (15 points) Each of \(450\) members of parliament slapped exactly one colleague. Prove that it is possible to choose a committee of \(150\) members such that no committee member has slapped another committee member.
Hint:
Make a graph where an (undirected) edge connects two people if one slapped the other. How many edges does each connected component have compared to its vertices? - (15 points) Let \(T\) be a tree on \(n\) vertices. For each edge \(e\), removing \(e\) splits \(T\) into two components of sizes \(a_{e}\) and \(n-a_{e}\). Prove that \[\sum_{e\in E(T)}a_{e}\ (n-a_{e}) \;=\; \sum_{\{u,v\}\subseteq V(T)}\operatorname{dist}(u,v).\]
- (15 points) A tree on \(n\) vertices is given. In one move, you may erase an edge incident to a leaf and then connect this leaf by an edge to any other vertex (vertices are unlabeled). What is the smallest number of moves that always suffices to transform any given tree on \(n\) vertices into any other given tree on \(n\) vertices?
- (15 points) Let \(T\) be a uniformly random labeled tree on \([n]\).
- find the distribution of \(\deg(1)\);
- compute \(E[\deg(1)]\) and \(\operatorname{Var}[\deg(1)]\);
- compute the expected number of leaves in \(T\).
- (15 points) Let \(G\) be a connected graph and \(T_{1},T_{2}\) two spanning trees. Show that \(T_{1}\) can be transformed into \(T_{2}\) by a sequence of edge swaps (add one edge, delete one edge) such that every intermediate graph is a spanning tree. Give a bound on the number of swaps in terms of \(|T_{1}\triangle T_{2}|\).
Hint:
Use the Prüfer code.