Let's say I have a graph that is not bipartite. Let's say it is colored red and black and there are some conflicts where two vertices of the same color share an edge. I can introduce a new vertex between them of the opposite color, breaking the edge into two. Now I have removed that conflict. I can continue doing this until the modified graph is bipartite.
How do you do this in a way to minimize the number of vertices added? I don't want to assume that the graph is already colored. That was just to help explain the process.