7
$\begingroup$

I've got an example for this question, but there are many different possibilites and I don't know how to show this for all graphs. Has got anyone any advice how to begin ?

Let $G=(V,E)$ be an undirect graph. Then there is a partition $V = V_1 \cup V_2$ of a vertices set, so that all vertices in $G[V_1]$ and $G[V_2]$ have got an even degree.

I draw it on paper, but how mentioned it, it's not proven for all and I don't know how. Thank you for any advice.

$\endgroup$
14
$\begingroup$

We approach this problem via induction on the number of vertices, $|V|$. Trivially, the claim is true when $|V|\leq 3$.

Assume for our induction hypothesis that all graphs on strictly fewer than $n$ vertices satisfies the claim that there exists some partition into two sets of vertices where the induced subgraph on each is such that every vertex is of even degree. Consider then what happens for arbitrary $G$ when $|V(G)|=n$.

We may assume that $G$ contains at least one vertex of odd degree (if not, then take $V_1 = V$ and $V_2 = \emptyset$, trivially satisfying the claim). Pick one such vertex of odd degree and label it $v$. Take note of the neighborhood of $v$ and label it $\mathscr{N}(v)$.

Construct a new graph from the original defined as: $G' = (V(G)\backslash\{v\}, \{(x,y):~x\neq y, (x,y)\in E(G\backslash \mathscr{N}(v))\cup (E(\mathscr{N}(v)))^c\})$

That is to say, to form $G'$, invert the adjacency relationships between members of $\mathscr{N}(v)$, delete $v$, and retain the rest of the graph the way it was in $G$.

Example

Now, $G'$ has fewer vertices than $G$ and by our induction hypothesis has some partition $V_1', V_2'$ such that all vertices in the induced subgraphs from $G'$ are of even degree.

Define $A = V_1'\cap \mathscr{N}(v)$ and define $B = V_2'\cap \mathscr{N}(v)$

As $v$ was selected to be of odd degree, precisely one of $|A|$ or $|B|$ will be of even size. Without loss of generality, assume it was $A$.

Returning now to the original graph, consider the partition $V_1 = V_1'\cup\{v\}$ and $V_2 = V_2'~~~~~$ (note, if it had been $B$ which was of even size, attach $\{v\}$ to $V_2$ instead)

partitioned

Note that for any vertex $x\in V_i\backslash\mathscr{N}(v)$, the adjacencies are the same as in the induced subgraph from $G'$ of $V_i'$, and is therefore of even degree.

For any vertex in $A$, It will have the same number of adjacencies to elements outside of $A$ as in the induced subgraph from $G'$ of $V_1'$ (either odd or even$\star$), and will have $|A\backslash\{x\}|$ minus the number of adjacencies to other elements of $A$ while in $G'$ (odd if $\star$ was odd, even otherwise), plus 1 for the adjacency to $v$. I.e., $d_{G(V_1)}(x) = d_{G'(V_1')}(x) + |A|-1-d_{G'(A')}(x)+1$ (which is even + even - 1 - even + 1 or it is odd + even - 1 - odd + 1) and is therefore of even degree.

For any vertex $x\in B$, as $|B|$ was assumed to be odd, it will similarly be $d_{G(V_2)}(x) = d_{G'(V_2')}(x) + |B|-1 -d_{G'(B')}(x)$ (which is even + odd - 1 - even or it is odd + odd - 1 - odd) and is also of even degree.

For $v$ itself, its only adjacencies are to $A$, which was assumed to be of even size, and so $d(v)=|A|$ is even.

Therefore, all vertices are of even degree in their respective induced subgraphs and the claim is proven.

$\endgroup$
2
  • $\begingroup$ Thanks a lot ! Really you helped me :) $\endgroup$ – pinkpanther5 Dec 13 '14 at 15:51
  • $\begingroup$ This is a great proof! thanks $\endgroup$ – user614287 Nov 29 '18 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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