# A problem of graph theory

Let $G$ be a finite graph, and $E$ the set of edges of $G$. For each vertex $a$, we denote that $E_{a}$ by the edges of $G$ which pass to $a$. Suppose for any $a \in G$, $\sharp E_{a} >3$. Let $f: E \longrightarrow$ {$1,2$}.

Does there exists a map $f$ such that for each $a$, $\sharp (f^{-1}(1) \cap E_{a})$ is a nonzero even number.

Thank you very much!

• As far as positive results go, I can prove the existence of $f$ if $G$ is $4$-edge-connected, but this is probably not quite optimal. – darij grinberg Jul 11 '12 at 10:04
• When $G$ is cubic, your question is equivalent to the existence of a perfect matching. Petersen's theorem says that it exists at least when $G$ is bridgeless. Again, that's not an if-and-only-if. – darij grinberg Jul 11 '12 at 10:12
• Thanks for your comment, darij. In fact, this problem arises from arithmetic geometry, I want to construct a special abelian covering of a stable curve which irreducible components are all projective line. – kiseki Jul 11 '12 at 10:20
• Here are some improvements on Petersen's theorem: mathoverflow.net/questions/98385 – darij grinberg Jul 11 '12 at 10:20
• mathoverflow.net/questions/98385 showed a conterexamples for my problem. But if the dual graph of a stable curves is the graph of mathoverflow.net/questions/98385, we could construct a abelian covering of the stable curve directly. So maybe we should assume for any vertex $a$ such that ♯Ea>3 – kiseki Jul 11 '12 at 10:55

The question is equivalent to the following: Let $G$ be a finite graph of valencies $\ge 4$. Does there exist a subgraph with the same set of vertices, of even, non-zero valencies? The way you construct such a subgraph is to delete edges. If you delete an edge that connects a point of odd valency to a point of even valency, you just move the "bad guy" of odd valency. But you can connect two points of odd valency by a shortest path and then delete all edges along the path. In this way you lose two "bad guys". However, if you iterate this, it might bring the valency of some vertices to zero. So the following is a counterexample: Let $C_4$ be the complete graph in for vertices and let $X$ be a graph in the shape of a cross. Then $X$ has 5 vertices. Take the 4 edges of valency 1 and join each to one copy of $C_4$, where you joint it to each vertex of $C_4$. You end up with a cross, where at each end you have one copy of $C_4$. The "bad guys" are the points that join the middle cross to the copies of $C_4$. This is easily seen to be a counterexample.