|
2
1
|
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! |
|||||||||||||||||||
|
|
1
|
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. |
||
|
|
