Converting a graph to a biparte to find the maximal matching Im trying to get the maximal matching via trial and error (for the matching problem) derived from the following graph: 

But before I do this, I know I need to convert it into a biparte graph? 
Ive constructed a biparte before by using independent sets, but here if i use {3,7,8} i get a very redundant biparte. Is there an algorithm for conversion?
I know this graph has a matching of size 4 {{1,2},{5,9},{6,10},{11,12}} but it is not maximal. The only way I can figure how the maximal can be found is by converting to a bipate, or is there another way?
Thanks in advance!
 A: To partition your bipartite graph, just take any vertex, say 1, put it in A, and put all its adjacent neighbours 2 and 4 in B. You continue until all the vertices are partitioned into one of A or B, if you run into trouble it's not a bipartite graph. 
Thus you will have: A = {1, 5, 3, 7, 8, 10, 11} and B = {2, 4, 6, 9, 12}. The maximum matching is size 5.
Now you find any matching, your current one is fine so let's use that. Mark the edges that are in that matching, {1,2},{5,9},{6,10},{11,12}.
Observe that there is an alternating path, 5 - 9, that starts and ends on vertices in the matching. 
Furthermore we can augment this alternating path since 5 connects to free vertex 4 and 9 connects to free vertex 8. 
We create the augmented path 4 - 5 - 9 - 8, and reverse the matching status of each edge each edge in the augmented path. Thus the matching in the augmented path becomes {{4,5},{8,9}}.
Our matching is now size 5, and includes {{1,2},{4,5},{6,10},{8,9},{11,12}}. This is the maximum matching.
