Partition a simple graph into vertex disjoint graph.

Question

Let's consider undirected simple and connected graph.

I want to partition the vertex set into a minimal number of disjoint subsets such that the induced graph of each subset has an even number of edges?

I observed that if we have at least one odd degree vertex then we can move it to a different set then set of all other vertices. In this case we will have at most 2 disjoint sets.

Now when we don't have any odd degree vertex we must have eulerian cycle.

Now we can find smallest odd length cycle. All vertices not in cycle will now receive same set(let say set number $1$). And we will pick two adjacent vertices in our cycle then all other vertex in cycle can now receive same set(let say $2$) because this two vertex will eliminate 3 edges from cycle. Now we have to check whether our selected 2 vertices have any common edges to vertex not in cycle if not we can assign them same set as non cycle vertex(i.e set $1$). (here noncyclic vertex is vertex not included in our smallest odd length cycle.)

I want to know whether my approach is correct or not. Any help and suggestion would be very appreciated.

Answer 1

For the first part, you are perfectly correct: any graph with an odd-degree vertex has a partition into at most $2$ such sets. I'd point out that here, we know that the partition we find is optimal, because:

• If the graph has an even number of edges, the trivial partition (with $1$ set) is optimal.
• If the graph has an odd number of edges, and $v$ is an odd vertex, the partition with $\{v\}$ and $V-\{v\}$ (everything else) is optimal, since the trivial partition doesn't work.

For the second part, I think I agree with the partitions you find, but you haven't shown they're optimal. In particular, sometimes you find a $3$-set partition, and you don't know that there's no $2$-set partition which works.

(By the way, there's a $3$-set partition which is a bit simpler: in the case of a graph where every vertex has even degree but the total number of edges is odd, let $vw$ be any edge, and take the partition into $\{v\}$, $\{w\}$, and everything else. This works!)

Actually, if the graph has an odd number of edges but all degrees are even, it's impossible for there to be a $2$-set partition which works, so this is best possible. Here's why.

Suppose that we partition the vertex set $V$ of a graph $G$ into $S$ and $V-S$. Then the number of edges going between $S$ and $V-S$ is equal to $$ \sum_{v \in S} \deg_{V-S}(v) = \sum_{v\in S}\deg(v) - \sum_{v\in S}\deg_S(v) $$ where by "$\deg_X(v)$" I mean the number of edges from $v$ to vertices in a set $X$. On the right-hand side, the first sum is even (because all degrees $\deg(v)$ are even) and the second sum is even (because it's twice the number of edges in the induced graph $G[S]$). Therefore the number of edges going between $S$ and $V-S$ is even.

All the edges of $G$ are either edges of $G[S]$, or edges of $G[V-S]$, or edges going between $S$ and $V-S$. We've just shown that the third category has an even number of edges - but the total number of edges is odd. So one of $G[S]$ or $G[V-S]$ has an odd number of edges, and we don't have a valid partition.