Help in a Graph question

[notacoder]

An undirected graph with N vertices (numbered 1 through N) and M edges. He wants to divide it into K parts (subgraphs) for some integer K.
An edge is said to be a part of a subgraph if its both the vertices is present in the subgraph.
The condition is that every subgraph should contain even number of edges belonging to it(zero edges is also considered even).We need to minimise the value of K.
Example: N=5,M=5
the edges: 1-2,1-3,2-3,2-4,3-4
output: K=2
the subgraph corresponding to which each vertices numbered from 1 to N belongs:
1 belongs to subgraph 1,2 belongs to subgraph 2,3 belongs to subgraph 1,4 belongs to subgraph 1,5 belongs to subgraph 2

[Duthomhas]

I can (and have) solved this before.

What have you done to try?

[notacoder]

>Duthomhas
I was basically thinking of taking the whole graph as one when the edges are even and when odd doing DFS and dividing accordingly but the case of disconnected graph was causing the problem.

[Duthomhas]

Er, ok, so I drew a picture of your graph.

1,5 cannot be a subgraph, that leaves 2,3,4 with three edges. Vertices 2 or 3 must be paired with 5. For example:

    {2,5|0 edges}, {1,3,4|2 edges}

Do you see a pattern you can exploit here?


[edit]
The graph described by 5V, 5E = 1-2, 1-3, 2-3, 2-4, 3-4:

(1)--(2)
 |  / |   (5)
 | /  |
(3)--(4)

[Duthomhas]

You are almost there. :O)

Draw pictures.

The write code.

[notacoder]

I didnt understand the logic behind the odd cycle case??

[Duthomhas]

Umm, what happened to this thread?