1
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Jul 11, 2012 at 10:04
  • $\begingroup$ 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. $\endgroup$ Jul 11, 2012 at 10:12
  • $\begingroup$ 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. $\endgroup$
    – kiseki
    Jul 11, 2012 at 10:20
  • 1
    $\begingroup$ Here are some improvements on Petersen's theorem: mathoverflow.net/questions/98385 $\endgroup$ Jul 11, 2012 at 10:20
  • 1
    $\begingroup$ 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 $\endgroup$
    – kiseki
    Jul 11, 2012 at 10:55

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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