Having trouble proving vertex cover greedy algorithm
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.