Bipartite graph with even degrees

Question

Given a bipartite graph with an equal number of vertices in its parts. Each vertex in the first part is connected with an even number of vertices in the second part. Prove that we can remove some (maybe none, but NOT all) vertices from the first part so that every vertex in the second part will have an even degree?

I tried to build an eulerian subgraph of such graph using some traverses like in Kuhns algorithm but got nothing good.

Answer 1

This just uses Pigeonhole Principle, but the underlying idea/approach is essentially the linear algebra solution, which is why I didn't write it up initially. Since Aryan added a PP solution, I thought I should add this.

Let the vertices of the bipartite graph be $ A \cup B$.
Let the pigeons be the $ 2^n - 1$ possible subsets of $A$.
Let the holes be the $2^n$ possible parities for the vertex degree of B.

Since each vertex in $A$ has even degree, the sum of vertex degrees in $B$ must also be even, which means that there are actually at most $2^{n-1}$ possible parities for the vertex degree of B.
Hence, by PP, there exist 2 distinct subsets of $A$, (which we call $A_1, A_2$,) that give the same parities for the vertex degree of $B$. Then, $A_1 \Delta A_2$ is a non-empty subset of $A$ whose vertex degree of $B$ is all even.

Answer 2

This is not true. Consider the complete bipartite graph $K_{2,2}$ and remove one vertex so the resulting graph is $K_{1, 2}$ and hence the vertices in the second part have degree 1.

Answer 3

Consider the incidence matrix $M$, where entry $M_{ij} = 1$ if the ith vertex in the first part is connected to the ith vertex in the second part, 0 otherwise.

Work in $ F_2$.

We are given that $ M \times 1 = 0$. (Translation: Each vertex in the first part is connected to an even number of vertices, which is 0 in $F_2$).
So $ \det(M) = 0$.
So there is a non-trivial left vector $a$ such that $ a M = 0 $.
Translating back, restricting to the vertices in the first part that correspond to a non-zero entry in the vector $a$, then every vertex in the second part is connected to an even number of these.

Answer 4

First of all let's say that the vertices are in two different groups $A,B$, size of each of them equal to $n$. Let's call the vertices in $B$ that have odd degree as bad vertices. Now since the sum of degrees of the vertices in the $A$ is even, (since the degree of each of them is even) the sum of degrees of the vertices in $B$ is even too. So clearly the number of bad vertices in $B$ is always even. Now let's evaluate the number of cases in which some of the vertices in $B$ can be bad vertices. (Through this solution we'll assume that there is at least one bad vertex in $B$ in the beginning of the problem. Otherwise we don't have to remove any of the vertices.) Since the number of bad vertices is even, the number of cases is equal to the number of subsets of $\{1,2,\dotsb,n\}$ with even number of elements and chosing zero vertices is not an option since it means that there are no bad vertices which we have discussed before. So the number of cases is equal to $$\binom{n}{2}+\binom{n}{4}+\dotsb=2^{n-1}-1$$
On the other hand the number of possibilities for removing a set of vertices in $A$ is equal to $2^n-2$. (not counting the cases in which none or all of the vertices are removed) Now for the sake of the contradiction, assume that none of these $2^n-2$ choices cause $B$ to have no bad vertices. Finally we conclude that according to the pigeonhole principle one of the following cases happen:

1. There are three of the $2^n-2$ cases that result in the same set of bad vertices in $B$.
2. For each set of vertices of $B$ like $S$ with even number of vertices, there are exactly two different choices of vertices of $A$ removing which the set of bad vertices is equal to the set $S$.

Before proving the cases note that if for two different sets $S_1,S_2$ of vertices of $A$, if $\{1,2,\dotsb,n\}-S_1\not =S_2$, then by removing the set of vertices in $A$ achieved by the binary sum of $S_1,S_2$ (which is neither containing all vertices nor an empty set), all of the vertices in $B$ will have even degrees.
Now the first case is trivial: Since there are three sets $S_1,S_2,S_3$ removing which will cause in the same set of bad vertices in $B$, by what we just said and because clearly $A+B=\{1,2,\dotsb,n\}$ and $A+C=\{1,2,\dotsb,n\}$ can't hold simultaneously, the case is proven.
But in the second case, note that if $S_1,S_2$ are the two sets removing which we'll have the same set of bad vertices in $B$, then $S_1+S_2\not =\{1,2,\dotsb,n\}$. (otherwise the case is proven) And because these two sets both have even number of elements $n$ is even, too. So we only have to prove the problem for even $n$.On the other hand if $n$ is even the set $\{1,2,\dotsb,n\}$ isn't counted in the number of sets with even number of elements. That's because if removing each of the sets $S_1,S_2$ such that $S_1+S_2=\{1,2,\dotsb,n\}$ results in all of the vertices of $B$ to have odd degrees, then it means that each vertex in $B$ is connected to odd number of vertices in $S_1$ and odd number of vertices in $S_2$ and hence each of the vertices in $B$ have even degrees and therefore this is equivalent to the case we ommited in the beginning. So once again, we assume that there are $2^n-2$ choices for removing some vertices of $A$ and $2^{n-1}-2$ choices for choosing an even number of vertices from the vertices of $B$ and hence by the pigeonhole principle, there are at least $\lceil \frac{2^n-2}{2^{n-1}-2}\rceil=3$sets of vertices in $A$ by removing which the same set of bad vertices in $B$ will be made and hence the problem will be solved by what we proved in the first case and therefore the proof is complete!