# Probabilistic Method – 4

February 10, 2011 1 Comment

Q.1. Prove that there exists a tournament on vertices having at least Hamiltonian paths.

Solution.

A tournament is an orientation of a complete graph. Let each of the edges be oriented, independently, in either direction with probability .

Take a random permutation, of the vertex set of the graph.

Let be a random variable denoting the number of Hamiltonian paths.

.

Q.2. Independence number is the size of a largest independent set of . Prove that for any graph having vertices, edges and average degree , .

Solution.

Let be formed by sampling each vertex of , independently, with probability . Let denote the number of vertices in , and , the number of edges in the subgraph induced by .

There exists a subset such that the difference between the number of vertices in and the number of edges in is at least .

Remove a vertex for each edge in until the resultant set is an independent set. (This procedure removes at least as many edges as vertices.)

Set .

There exists an independent set of size at least .

Pingback: Probabilistic Design ebook : Cars Blog | Everything You should Know about Cars