Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.
1. A Hamiltonian path in an undirected graph G = (V,E) is a path that goes through every vertex exactly once. A Hamiltonian cycle (or Hamiltonian tour) is a cycle that goes through every vertex exactly once. Note that, in a graph with n vertices, a Hamiltonian path consists of n−1 edges, and a Hamiltonian cycle consists of n edges. Prove that for every n ≥ 2, the n-dimensional hypercube has a Hamiltonian cycle.
Base case: n=2, a two dimensional hypercube is just a square, so we can just take a clockwise path from any specific vertex.
Inductive Hypothesis: Assume this is true for all dimensions up to n-1.
Inductive step: Suppose now that every (n − 1)-dimensional hypercube has an Hamiltonian cycle. Let v ∈ {0,1}n−1 be a vertex adjacent to 0n−1 (the notation 0n−1 means a sequence of n−1 zeroes) in the Hamiltonian cycle in a (n−1)-dimensional hypercube. The following is a Hamiltonian cycle in an n-dimensional hypercube: have a path that goes from 0 n to 0v by passing through all vertices of the form 0x (this is simply a copy of the Hamiltonian path in dimension (n−1), minus the edge from v to 0 n−1 ), then an edge from 0v to 1v, then a path from 1v to 10n−1 that passes through all vertices of the form 1x, and finally an edge from 10n−1 to 0n 2. A tournament is defined to be a directed graph such that for every pair of distinct nodes v and w, exactly one of (v,w) and (w, v) is an edge (representing which player beat the other in a round-robin tournament). Prove that every tournament has a Hamiltonian path. In other words, you can always arrange the players in a line so that each player beats the next player in the line.
Base case: With either 0 players or 1 player, the base case trivially holds.
Induction Hypothesis: Assume that this is true for all values less than or equal to n-1.
Inductive Step: Let's look at a tournament with n players and take on specific player. Take this player out of the game and create two sets: one which beat this player and one who this player beat. By the induction hypothesis, we can arrange both of these sets so that each player beats the next player. Now, place our current player between the last person in the set who beat our current player and the first person in the set who our current player beat. We now have a directed graph in which every player beats the next person in the line for n players, and hence, by induction, it is true for all n. 3. Show that every simple finite graph has two vertices of the same degree.
This can be shown using the pigeon hole principle. Assume that the graph has n vertices. Each of those vertices is connected to either 0, 1, 2, . . . , n − 1 other vertices. If any of the vertices is connected to n − 1 vertices, then it is connected to all the others, so there cannot be a vertex connected to 0 others. Thus it is impossible to have a graph with n vertices where one is vertex has degree 0 and another has degree n − 1. Thus the vertices can have at most n − 1 different degrees, but since there are n vertices, at least two must have the same degree.