Vertex Cover approximation algorithm
You ask for a graph where your (nondeterministic) algorithm gives the optimal solution even in the worst case. We're looking for a set of vertices that cover all edges. The difficulty with your algorithm is not only that it could pick the edges in an "inconvenient" order, but also that it adds both vertices belonging to the edge, which is suboptimal in most cases (since adding one of the vertices already covers the edge).

An example where your algorithm does always find the optimal solution of size 10, is the graph below. If you meant the problem the other way around (cover all vertices), the same graph applies.