You are given a very special graph. The vertices of the graph come in three columns: left, center, and right. The edges connect vertices from the left to vertices in the center, and from the center to the right; there are no left to right edges. The graph also has the property that it does not contain any “closed diamonds”, meaning there are never two routes from a vertex on the left to a vertex on the right. See sample graphs

You are asked to prune the graph following these rules. For each left vertex, remove all but one of its outgoing edges. When you remove a (left,center) edge, then also remove the corresponding center vertex. When you remove a center vertex, then also remove all of its (center,right) edges and the corresponding right vertices.

Is it possible in this way to remove all of the right vertices? If so, give an example. If not, prove it. (I believe it is not possible, and I’m looking for a proof.)

  • $\begingroup$ arent both of your OK sample graphs counter-examples? What if all the vertices on the left have degree $1$ at the start? Then you don't remove anything. $\endgroup$ Sep 27 '18 at 6:18
  • $\begingroup$ "very special" is over-valued. $\endgroup$ Sep 29 '18 at 11:01

I guess the question is whether there is any graph that allows removing all its right vertices. There are plenty, for example the complete bipartite graph $K_{2,2}$ on the left and center augmented with two vertices on the right and two parallel edges between the center and the right. Your rules allows removing the two parallel edges in $K_{2,2}$, thus removing all center and right vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.