<p>Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit the edge $e$ and we let it die (sorry about that).
At the end of the process, we consider the set of survived edges $S$ and we look at the graph $G[S]$ consisting of survived edges only. Let $C_1, \ldots, C_n$ be the connected components of $G[S]$ and let $e=(u,v)$ be a dead edge: we say that $e$ died with honor if there exists just a single component $C_i$ s.t. $u,v\in C_i$, that is $e$ dies with honor if it doesn't connect two different components of the survived edges graph.</p>

<p>What can we say about the probability $P_H$ of the event $H=$"all the bad edges $B$ are dead and at least one died with honor" ? Can we lower bound somehow this probability as a function of $k$ ? Can we find structural hypothesis over $G$ or particular distributions for random $G$ in order to do that ? </p>

CC BY-SA 3.0
2014-01-24T22:46:42.600Z
I love the phrase, but I'm curious about the motivation for it. Why does an edge "die with honor" in this case ? i.e why is it dishonorable for an edge to have died disconnecting two components ?
Suresh Venkat
CC BY-SA 3.0
2014-01-25T09:27:23.033Z
The colorful phrase comes from the fact that at the end of the process we would like to distinguish bad dead edges from the good dead ones, but we can look what is going on just inside the connected components. So if a bad edge dies inside a connected component we can recognize that it was indeed bad.
XORwell
CC BY-SA 3.0
2014-01-25T18:11:48.960Z
Ah. so "died with dishonor" means "could not be identified". Gruesome, but I get it.
Suresh Venkat
CC BY-SA 3.0
2014-01-25T18:50:50.220Z
means "it was bad, but it could not be identified"... I can rephrase...
XORwell
CC BY-SA 3.0
2014-01-25T20:23:37.630Z
I might not understand the question but if G is a cycle and k is at least 2, then this probability is zero.
domotorp
CC BY-SA 3.0
2014-01-25T22:57:27.660Z
Right, I guess this is a first answer to the question "can we find structure over $G$ in order to say something?" :-P
XORwell
<graph-theory><randomized-algorithms>
Hitting edges in graphs at random and let them die with honor
XORwell
# Hitting edges in graphs at random and let them die with honor

(Asked by: username_0 on 2014-01-24)

Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit the edge $e$ and we let it die (sorry about that).
At the end of the process, we consider the set of survived edges $S$ and we look at the graph $G[S]$ consisting of survived edges only. Let $C\_1, \ldots, C\_n$ be the connected components of $G[S]$ and let $e=(u,v)$ be a dead edge: we say that $e$ died with honor if there exists just a single component $C\_i$ s.t. $u,v\in C\_i$, that is $e$ dies with honor if it doesn't connect two different components of the survived edges graph.

What can we say about the probability $P\_H$ of the event $H=$"all the bad edges $B$ are dead and at least one died with honor" ? Can we lower bound somehow this probability as a function of $k$ ? Can we find structural hypothesis over $G$ or particular distributions for random $G$ in order to do that ?

**Tags:** graph-theory, randomized-algorithms

> **Comments:**
> **username_1**: I love the phrase, but I'm curious about the motivation for it. Why does an edge "die with honor" in this case ? i.e why is it dishonorable for an edge to have died disconnecting two components ?  
> **username_0**: The colorful phrase comes from the fact that at the end of the process we would like to distinguish bad dead edges from the good dead ones, but we can look what is going on just inside the connected components. So if a bad edge dies inside a connected component we can recognize that it was indeed bad.  
> **username_1**: Ah. so "died with dishonor" means "could not be identified". Gruesome, but I get it.  
> **username_0**: means "it was bad, but it could not be identified"... I can rephrase...  
> **username_2**: I might not understand the question but if G is a cycle and k is at least 2, then this probability is zero.  
> **username_0**: Right, I guess this is a first answer to the question "can we find structure over $G$ in order to say something?" :-P  

---

## 0 answers

