We choose each edge in a graph $G$ (with $m$ edges) at random independently with probability $p\in[0,1]$. What is a probability that we chose an even number of edges at the vertex $v$ which has degree $k$.

Let $X$ be a number of chosen edges at $v$ and let $q=1-p$. $$\begin{eqnarray} P(X=\;{is\; even}) &=& P(X=0)+P(X=2)+P(X=4)+P(X=6)...\\ &=& {k\choose 0}p^0q^k +{k\choose 2}p^2q^{k-2}+{k\choose 4}p^4q^{k-4}+...\\ &=& {1\over 2}\Big( (q+p)^k+(q-p)^k\Big)\\ &=& {1\over 2}\Big( 1+(1-2p)^k\Big) \end{eqnarray}$$ Edit: Thanks to Henry I will continue with my second question right here.

Prove that probability that we choose at each vertex odd number of edges if a graph $G$ is connected and with $2n$ vertices is nonzero.

$P(G \;is \;''odd'') = 1-P(G\;is \;not "odd") $

$$\begin{eqnarray} P(G\;is\;not\;"odd") &=& P(X_1 = even\;or\;X_2=even \;or\; X_3=even...)\\ &\leq & P(X_1 = even)+P(X_2=even) + P(X_3=even)+...\\ &=& {1\over 2}\sum_{i=1}^{2n} \Big( 1+(1-2p)^{d_i}\Big) \end{eqnarray}$$ where $d_i$ is a degree of vertex $v_i$. I'm stuck here, don't know how to show that this is (if it is) smaller than $1$ for some sutabile $p$. I know, that since $G$ is connected we have $m\geq 2n-1$.

Edit: (1.23.2019) Does anyone see how could this aproach be saved?

  • 2
    $\begingroup$ Apart from a missing $P(X=0)$ at the start (now edited in), this looks sensible $\endgroup$ – Henry Dec 27 '18 at 23:19
  • $\begingroup$ What range is $p$ in? If $p \le 1/2$ then the sum is at least $n$... $\endgroup$ – Sandeep Silwal Dec 28 '18 at 1:31
  • $\begingroup$ Your second question appears to be equivalent to your earlier question from a few days ago: math.stackexchange.com/questions/3052416 (That is, assuming $p \ne 0,1$. If $p=0$ or $p=1$ the probability might be $0$.) $\endgroup$ – Misha Lavrov Dec 28 '18 at 3:02

Unfortunately, the last sum is not necessarily less than $1$.

Say we have the line graph with $2n$ vertices. Then two vertices has a degree $1$ and the other $2$. So we have: $${1\over 2}\sum_{i=1}^{2n} \Big( 1+(1-2p)^{d_i}\Big) = (n-1)x^2+x+n =:f(x)$$

where $x = 1-2p$. But $f(x)$ can not be $<1$ since the inequality $ f(x)<1 $ is equivalent to $$ (n-1)x^2+x+(n-1)<0$$ and the discirminat is $1-4(n-1)^2<0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.