FS19 Comsol

1

b)

For every connected graph $G$ with $n$ nodes: if $G$ has a cycle of length $k$, $n>k$, it has a path of length $k+1$

Proof: Let $C=\{v_1,v_2,\dots ,v_k\}$ be a cycle with $|C|=k$ exists. As $n>k$ there is at least one more node, let’s call it $u$.

• As $G$ is connected, there is a path from $u$ to all $v_i\in C$.
• WLOG we assume $u$ is a neighbour of $v_1$.
• Then $P=\{u,v_1,v_2,\dots ,v_k\}$ is a path of length k+1

e)

Let $G$ be a grpah with $n\ge 3$ nodes and $\mathrm{deg}(v)\ge \frac{n}{2}$ for all $v\in V$.

This graph is connected as $\delta (G)\le \frac{n}{2}$ which implies by Dirac’s Theorem that $G$ is hamiltonian, which means that there is a path from every vertex to eveyr other $⟹$ $G$ connected.

4

$G$ k-regular Graph with $n$ nodes. It has exactly $m=nk/2$ edges. We randomly choose for each edge if it’s marked or not with probability $p$. For a node with multiple incident marked edges, we remove one at random.
This finds a valid matching $M$.

b)

Let $Y$ be the number of unordered pairs of edges $\{e_1,e_2\}\subset E$, s.t. $e_1\ne e_2$, $e_1,e_2$ both marked and $|e_1\cap e_2|$ share a common endpoint. Find $\mathbb{E}[Y]$.

Let $Y_i$ be the indicator variable for pair $i$ of edges to be both marked. Then $\mathbb{E}[Y_i]=p^2$.

There are $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ ways to choose pairs of edges that share and endpoint on each node. Thus there are $n\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ in total.

Thus $\mathbb{E}[Y]={\sum }_{i=1}^{2\left(\genfrac{}{}{0ex}{}{k}{2}\right)}\mathbb{E}[Y_i]=n\left(\genfrac{}{}{0ex}{}{k}{2}\right)p^2=nk(k-1)p^2$.

c)

The greedy selection algorithm deletes at most $1$ edge from each pair counted in $Y$ per turn. Thus we are left with $|M|\ge X-Y$ edges at the end.

• we delete at most one edge for each conflict.

$\mathbb{E}[X-Y]=\mathbb{E}[X]-\mathbb{E}[Y]=\frac{nk}{2}p-nk(k-1)p^2$.
We derive with respect to $p$ and find that $p=\frac{1}{2(k-1)}$ maximises the number of $X-Y$.
Thus $\mathbb{E}[X-Y]=\frac{nk}{2}\frac{1}{2(k-1)}-nk(k-1)\frac{1}{4(k-1{)}^2}=\frac{n}{8}$.