MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, everyone, I want to ask a question about 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!

share|cite|improve this question
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: – darij grinberg Jul 11 '12 at 10:20
1 showed a conterexamples for my problem. But if the dual graph of a stable curves is the graph of, 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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