Dividing a graph into an even and an odd graph

combinatoricsgraph theory

Suppose $G(V,E)$ be a simple graph. Prove that there is always a subset of $V(G)$ like $X$ such that all vertices in $G[X]$ are even and all vertices in $G[V\setminus X]$ are odd.

  • a vertex is even (odd) iff its degree is even (odd).

A similar problem that I could solve is that we can divide a graph into two even graphs and I solved it by induction on number of vertices. Supposing if it has any odd vertice $x$ then we put it aside and take the complement of its neighbours in $G-x$. But I couldn't solve this one I shared above. I would be thankful if you help me solve it.

my approach for two even graphs:

for the two even division part, I use induction and say suppose for all graphs with less than n+1 vertices this is correct (the base case is isolated graph). now consider G have n+1 vertices. if all of them are even we are fine. Suppose x is a vertex with odd deg. now take it out and let H be its neighbours. put its complementary instead and have a graph G' with n vertices. Now based on our assumption on induction we can divide G' into two even parts. because x was odd deg, one part of G' must have even number of x neighbours and other part must have the rest (which is odd). adding x to even part and considering the complement of complement of neighbours of x (which is the original neighbours) we will get the graph we want. so it's done.

source:
this is a problem I found in an old olympiad note (maybe for 2009) but it doesn't have answers. I solved the first part but I don't know how to write the second part (which I asked here)

Best Answer

If we can solve the problem for the two-even-subgraphs case, then this problem follows as a corollary.

Given a graph $G$, let $G+K_1$ be the graph obtained from $G$ by adding a single new vertex adjacent to all existing vertices of $G$. By assumption, we can find a subset $X \subseteq V(G + K_1)$ such that the subgraphs of $G+K_1$ induced by $X$ and by its complement are both even.

If we go back to $G$, deleting the extra vertex we added, then:

  • The subgraph induced by the set not containing the extra vertex is unchanged. It was previously even, so it stays even.
  • The subgraph induced by the set containing the extra vertex loses it. The degree of every vertex decreases by $1$, so every degree becomes odd.

Therefore we get an even-odd division of the original graph $G$.

Related Question