I'm afraid it's impossible to understand without some math notation :)

Denote X and Y as sets in bipartite graph (so from now we only have edges between X and Y). When you constructed maximum matching, you might want to decide (for every edge in this matching) which one of the incident vertices to pick to your minimum cover (we're going to pick only one vertex). How can we decide?

So let U and V be the vertices in matching from X and Y correspondingly. The answer for the current (u,v) edge from matching is simple: we just check number of vertices from Y\V that are adjacent to vertice "u" (num(u)) and similar for "v" (num(v)). After that we pick the vertice that has nonzero num function.

P.S. 1)Note, that it's impossible situation when both num(u) and num(v) are nonzero (leads to contradiction connected with maximum matching). 2)If both values are zero, it's up to you which vertice to choose :)

Suppose you have left and right parts in bipartite graph and you found the maximum matching M.

Let's define orientation of edges. Those edges that belong to M will go from right to left, all other edges will go from left to right.

Now run DFS starting at all left vertices that are not incident to edges in M. Some vertices of the graph will become visited during this DFS and some not-visited.

To get minimum vertex cover you take all visited right vertices of M, and all not-visited left vertices of M.

You can prove the correctness of this algorithm by contradiction. Take some edge (l,r) that was supposedly not covered and consider all four cases regarding l and r being incident to edges in M or not. In all these cases there should be a contradiction with the way we did DFS and the fact that M is a maximum matching.

LOL I've been through your struggle before and it took me a long while to understand the proof!

Let's see:

First, you can never get a vertex cover of size less than the maximum matching. Proof by contradiction: Assume you had a vertex cover, then for each edge in the maximum matching, it must be covered by either the node on the LEFT or the RIGHT of the bipartition. Therefore either the left node or the right node of every edge in the maximum matching is in the vertex cover. Then for each edge you need to pick at least one node in your vertex cover. Assuming you claim to have a vertex cover of size less than the maximum matching then at least one edge of the maximum matching is not covered and this is a contradiction! (Remember that every edge in the maximum matching is matched to two distinct nodes that are never incident to any other edge in the maximum matching)

This proves that the lower bound of the minimum vertex cover is at least as the maximum matching.

Now we need to prove that it's exactly of maximum matching size, therefore we need to show a correct algorithm that's given a maximum matching, is able to construct a vertex cover of the same size as the matching.

Going by the same logic, then, for each edge in the maximum matching, we should EITHER take its LEFT or RIGHT node but NEVER take both! Because if we take both then our vertex cover will never be of the same size as the matching because each edge in the matching has to be covered.

According to our logic, can you tell what nodes are DEFINITELY in the vertex cover? The answer is yes, these are the nodes that are incident to some matched edge and also are incident to unmatched edge that goes to an unmatched node! (Because they might be incident to some unmatched edge that goes to a matched node that's matched with some of it's other edges)

Those nodes are definitely in the vertex cover.

Let's look at our graph G.

Now we will do some kind of a special traversal over this graph that goes as follows, we will start at unmatched nodes on the left, follow their unmatched edges that gets us to the right. Then from the right nodes, we will follow only matched edges (obviously there is only one such edge for any right node).

So in short, when you are on LEFT node follow unmatched edges, when you are on RIGHT node follow the matched edge.

Your sequence of visiting will look like this

LEFT node --unmatched edge--> RIGHT node --matched edge--> LEFT node --unmatched edge--> RIGHT node ....... etc

Now what do we know? The first node on our path (Left node) is unmatched and also not in our vertex cover, we also (by our logic) know that the first right node on the path MUST be in our vertex cover (Re read past paragraphs if not sure why). Now we will take a matched edge back to the left part, what do we know about this left node? It's NEVER in our vertex cover since we covered that edge already with the RIGHT node!

A pattern will start to emerge when you follow this sequence. It turns out that all the left nodes you end up on ARE NOT in your cover while the RIGHT ones are in it!

Now we have covered many edges while also still adhering to our golden rule (Every matched edge can have EXACTLY one of its endpoints in our vertex cover)

Let's denote the nodes we visited during our procedure by 'A' and the ones that weren't by 'B'.

So during our exploration, we visited LEFT^A and RIGHT^A while we didn't visit either LEFT^B nor RIGHT^B.

Now we know that all of LEFT^A are NOT in our vertex cover while all RIGHT^A are in it!

Now what left? Only LEFT^B and RIGHT^B which weren't visited during our exploration!

Here comes the best part. You can safely take all LEFT^B in your vertex cover!! First let's prove that this is a vertex cover then we'll prove it's minimal.

First let's note that the set of nodes we taken COVER all of the matched edges, since for each edge we have either its left node or right node.

Assume now our nodes don't form vertex cover, then we have some UNMATCHED edge that's not covered by any node that we have. We will prove now these edges do NOT exist!

Now, for every unmatched edge that we passed over during our first procedure, we are sure that we have already covered that edge! Since we always included its RIGHT node in our cover.

Then only UNMATCHED edges that were NOT visited during our first procedure are the ones that might be uncovered.

What do these edges share in common?

Answer First: Their left endpoints are NOT unmatched! If they were unmatched then we would've visited these edges during our first procedure!

Therefore, their left endpoints are MATCHED.

Second: Since they are uncovered, then their left endpoints are NOT in LEFT^B and their right endpoints are NOT in RIGHT^A since we took all nodes in LEFT^B and RIGHT^A hence covered these edges.

Therefore their endpoints MUST be in LEFT^A and RIGHT^B so they can be uncovered!

So what these edges exactly are is:

They are UNMATCHED edges, and their left endpoint is in LEFT^A and their right endpoint is in RIGHT^B.

Now it's very easy to see that such edges do NOT exist according to our procedure of exploration because all unmatched edges that are incident to LEFT^A, their right endpoints must be in RIGHT^A.

Now we'll prove it's minimal, we need to show that for each matched edge, we never included both of it's left endpoint and right end point in our vertex cover.

Clearly, these are the edges that are matched and have their left end points in LEFT^B and their right and points in RIGHT^A.

It's also easy to see that these edges do NOT exist according to our exploration procedure since for all matched edges that are incident to RIGHT^A, their left points are in LEFT^A

Sorry for the lengthy proof!

EDIT: Added the proof it's minimal