Having trouble proving vertex cover greedy algorithm So this is my first time posting, but I don't know where else to go. I've spoken with several PHD and Masters students and they referred me here. I've been looking at the Vertex Cover problem and came up with an algorithm to find the optimal minimum. I've tried this on several graphs as examples and it's found the optimal every time. Could someone please help me prove that either this finds the optimal for all VC problems or if there is a counter example disproving it? Thanks in advance.

Given Graph G = (V,E), find minimum Vertex Cover


Sort the vertices by the number of edges associated; greatest to smallest O(nlogn)
While there are unmarked edges in E: O(V)


Select the vertices with the highest edge count (total), put vertex in set S, and mark it’s associated edges O(V*E)
Break ties by prioritizing the vertices with the fewest marked edges. If a tie still exists, handle arbitrarily. 
Skip vertices that have no unmarked edges. 

For each vertex in S, in the order they were added:


Remove vertex from set S and update edge markings. If any associated edge becomes unmarked, reselect vertex and remark the edges. Otherwise, remove vertex from S (nobody wanted them anyways ) O(V*E)

Return S


Algorithm runs in O(V*E). The edge markings can be maintained in a VxV table.
I had initially missed parts 2.3 and 3.

If I'm not still missing something, then your algorithm can find a non-optimal cover for the hexagon, and necessarily finds a non-optimal cover for ​ $K_{3,3}$ minus one edge. (Those are both connected balanced-bipartite graphs, so each half of their bi-partitions is a three-vertex vertex cover.)

The hexagon's vertices all have degree two, so "highest edge count (total)" ​ won't do anything, and your algorithm will fall back on 2.2 for each loop through 2. Your algorithm's initial choice for the hexagon doesn't matter, and its next choice will be an arbitrary one of the three vertices in the hexagon's opposite half. If your algorithm chooses the middle of those three ​ (i.e., the opposite vertex), then its next choice won't matter and part 2 will finish by choosing an arbitrary one of the vertices in the remaining unmarked edge. If its last choice is the one that is opposite from its next-to-last choice, then S will be the four vertices vertices from two opposite edges, which is a minimal vertex cover, in which case part 3 can't remove anything.

$K_{3,3}$ minus one edge has four vertices with degree three and no vertices with higher degree.Those four vertices are each adjacent to a degree-two vertex, so will all be put into S. Due to the removed edge, putting those four in will result in there being no unmarked edges. Since only that edge was removed, S is a minimal vertex cover, so part 3 can't remove anything from it.