# Probability that we choose even edges for a vertex

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?

• Apart from a missing $P(X=0)$ at the start (now edited in), this looks sensible – Henry Dec 27 '18 at 23:19
• What range is $p$ in? If $p \le 1/2$ then the sum is at least $n$... – Sandeep Silwal Dec 28 '18 at 1:31
• 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$.) – 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$$.