1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ At first I was little surprised that k is atmost 3. But now i have a proof. Thanks for quick reply. Little question in point 1. by complement of $\{u, v, w\}$ do you mean graph obtained by eliminating each vertex which is in $\{u, v, w\}$ and every edge incedent to one of the vertex in that set from original graph? $\endgroup$ – asdf_06 Oct 10 '19 at 3:24
  • $\begingroup$ Well, I mean that if the vertex set is $V$, the partition we take has the two sets $\{u,v,w\}$ and $V - \{u,v,w\}$. But then the subgraph induced by $V - \{u,v,w\}$ is the graph you describe, yes. $\endgroup$ – Misha Lavrov Oct 10 '19 at 3:29
  • $\begingroup$ Can you please point out what is going wrong here? $(1,4)$ $(1,2)$ $(2,3)$ $(3,4)$ $(4,6)$ $(4,8)$ $(6,5)$ $(6,7)$ $(6,8)$ $(5,8)$ $(7,8)$ in this graph where $V = \{1,2,3,4,5,6,7,8\}$ if we take $u=1$ , $v=4$ and $w = 3$. $V - \{u,v,w\}$ have odd number of edges. $\endgroup$ – asdf_06 Oct 10 '19 at 11:48
  • $\begingroup$ You're absolutely right - it was my mistake. Actually in the case left to consider (G has an odd number of edges, but all degrees are even) there is no possible $2$-set partition that works, and I've updated my answer with a proof. $\endgroup$ – Misha Lavrov Oct 10 '19 at 14:33
  • $\begingroup$ But how can we determine which vertex is going in which set when k=2 partition is impossible?kindly elaborate the process of 3 partition to determine the set of vertices. $\endgroup$ – sub_junc Oct 10 '19 at 15:50

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.