### Problem For $$n > 4$$, let $$DL_n$$ be the graph on $$n$$ vertices formed by taking $$L_n$$ and adding in the edges of $$(L_n)^2$$. For reference, $$DL_6$$ is drawn below: $$\begin{tikzpicture} \foreach \x in {1,2,3,4,5,6} { \draw[fill] (\x,0) circle (2pt); } \foreach \x in {1,2,3,4,5} { \draw (\x,0) -- (\x+1,0); } \foreach \x in {1,2,3,4} { \draw (\x,0) edge[bend left] (\x+2,0); } \end{tikzpicture}$$ 1. A set of **two edges**, chosen uniformly at random, is deleted from $$DL_n$$. What is the probability that this disconnects the graph? 2. A set of **two vertices**, chosen uniformly at random, is deleted from $$DL_n$$. What is the probability that this disconnects the graph? ### Solution Part 1 There are two ways of removing two edges to disconnect the graph: remove the two left-most or right-most edges., i.e. both edges incident to the same degree-2 vertex. The total number of edges is $$n-1$$ edges from $$L_n$$ plus $$n-2$$ edges from $$(L_n)^2$$, for a total of $$2n-3$$. This means there are $$\binom{2n-3}{2}$$ ways of choosing two edges, so the probability of disconnecting the graph is $$\frac{2}{\binom{2n-3}{2}}$$. (Bonus: simplifying) $$\frac{2}{\binom{2n-3}{2}}=\frac{2}{(2n-3)!/(2!\cdot(2n-5)!)}=\frac{2}{(2n-3)(2n-4)/2}=\frac{4}{(2n-3)(2n-4)}$$ Part 2 Removing any pair of adjacent vertices which do not include one of the two on the far ends will disconnect the graph (and removing no other pair will do so). There are $$n-3$$ such pairs. The total number of vertices is $$n$$, which means there are $$\binom{n}{2}$$ ways of picking two vertices to remove. And so, the probability is $$\frac{n-3}{\binom{n}{2}}$$. Bonus: simplifying $$\binom{n}{2}=(n)(n-1)/2$$ $$\frac{n-3}{\binom{n}{2}}=\frac{2(n-3)}{n(n-1)}$$