# $q$-connectedness of random digraphs obtained from a fixed graph

Let $G = (E,V)$ be an undirected graph (which can have multiple edges or loops).

Let $k,l,m\colon E\to \mathbb{R}_{\geq 0}$ be three edge-weight functions that satisfy $2k(e) + l(e) + m(e) = 1$ for all edges $e \in E$. Let $D_G(k,l,m) = (V,A)$ be the random digraph obtained from $G$ in the following manner: independently for each edge $e = \{u,v\} \in E$, remove $e$ and replace it with:

1. the arc $(u,v)$ with probability $k(e)$;
2. the arc $(v,u)$ with probability $k(e)$;
3. nothing with probability $l(e)$;
4. both arcs $(u,v)$ and $(v,u)$ with probability $m(e)$.

For a choice of root $q \in V$, we say a digraph $D = (V,A)$ is $q$-connected if there is a directed path from $q$ to every vertex $v \in V\setminus \{q\}$.

Proposition: $\mathrm{Pr}(D_G(k,l,m) \textrm{ is$q$-connected}) = \mathrm{Pr}(D_G(k',l',m') \textrm{ is$q'$-connected})$ if $k(e) + l(e) = k'(e) + l'(e)$ for every edge $e \in E$.

I know that this proposition is true; it follows from the discussion in Remark 5.4 of this paper. Basically the reason it is true is because both probabilities can be computed via a deletion-contraction recurrence.

But I would like to know if there is a simpler/more conceptual reason why this probability should be independent of the particular distribution $(k,l,m)$ so long as $k(e) + l(e)$ is fixed. (It is pretty easy to see, via path-reversals'', why it is independent of the choice of root $q$.)

Here is one heuristic reason why we might expect this probability to depend only on $k(e) + l(e)$. Fix a root $q \in V$. Let us say a cut $C = \{U,W\}$ of $G$ is bad for a digraph $D = (V,A)$ if $q \in U$ and there are no arcs from $U$ to $V$ in $D$. Observe that $D$ is $q$-connected iff it has no bad cuts. And the probability a given cut $C$ is bad for $D_G(k,l,m)$ is $\prod_{e \in \mathrm{cutset}(C)} (k(e) + l(e))$. But this is not a rigorous proof that $k(e) + l(e)$ is all that matters because clearly the events of $C$ and $C'$ being bad for $D_G(k,l,m)$ are not independent.

Instead of thinking of the initial graph as undirected, replace each edge with directed edges in each direction. The meaning of $k(e)+l(e)$ is the probability that you remove the directed edge $uv$. (You also want to assume the probability of removing $vu$ stays the same.)
Choose any edge $e$. Condition on the rest of the graph. The conditional probability that the graph is $q$-connected is one of $0$, $1$, the probability of including $uv$, or the probability of including $vu$. It can't be that you need to add both $uv$ and $vu$ to connect $q$ to everything since a path from $q$ through $e$ has to connect $q$ to one of the vertices $u$ or $v$ first. If $q$ is connected to $u$, then $vu$ is redundant, and if $q$ is connected to $v$, then $uv$ is redundant. So, the probability that the graph is $q$-connected only depends on the probabilities of including the edges $uv$ and $vu$ separately, not the probability of including both at the same time.
Given two functions that produce the same probabilities of removing each directed edge, the probability that the graph is $q$ connected does not change as you change the probabilities one edge at a time to convert one function to the other.