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?
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$.