# Probabilistic Method – 4

Q.1. Prove that there exists a tournament on $n$ vertices having at least $\frac{n!}{2^{n-1}}$ Hamiltonian paths.

Solution.

A tournament is an orientation of a complete graph. Let each of the $n \choose 2$ edges be oriented, independently, in either direction with probability $1/2$.

Take a random permutation, $\sigma$ of the vertex set of the graph.

$Pr[ \sigma \mbox{ represents a Hamiltonian path} ] = \frac {1}{ 2^{n-1}}.$

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

$\therefore E [X] = \frac{n!}{ 2^{n-1}}$.

$-$

Q.2. Independence number $\alpha(G)$ is the size of a largest independent set of $G = (V,E)$. Prove that for any  graph $G$ having $n$ vertices, $m$ edges and average degree $d = \frac{2m}{n} \leq 1$, $\alpha(G) \geq \frac{n} {2d}$.

Solution.

Let $S \subseteq V$ be formed by sampling each vertex of $G$, independently, with probability $p$. Let $X$ denote the number of vertices in $S$, and $Y$, the number of edges in the subgraph $G[S]$ induced by $S$.

$\therefore E[X] = np \mbox{ and } E[Y] = m p^2 = \frac{1}{2} n d p^2.$

$\therefore E[X- Y] = np(1 - dp/2).$

$\therefore$ There exists a subset $S \subseteq V$ such that the difference between the number of vertices in $S$ and the number of edges in $G[S]$ is at least $np(1-dp/2)$.

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

Set $p =1/d$.

$\therefore$ There exists an independent set of size at least $\frac{nd}{2}$.