# Integer linear programming (ILP) formulation of connectivity of induced subgraph

Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $$0$$, $$1$$ and $$2$$ and want the subgraph of graph $$(V,E)$$ made by same vertex set but edge set being those which have at least one end point as $$1$$ or $$2$$, to be connected. I don't need objective functions, just want to know how to show this as a constraint.

• Your title says induced subgraph, but your description says the same vertex set. Are vertices with label 0 and no neighbors with label 1 or 2 supposed to be included? Feb 7 '20 at 13:03
• @RobPratt No, those vertices need not be included. But based on some other constraints I am getting all the vertices. So, to simplify I have told that people need not worry about reduced vertices and vertex set remains same. Feb 7 '20 at 15:02
• I had asked a similar question about two years ago: mathoverflow.net/questions/282302/… Feb 7 '20 at 19:25
• you can find an answer also here: mathoverflow.net/a/282317/31310 Feb 7 '20 at 19:36