Let G = (V,E) be a graph. Consider variables xe associated with each edge e E....

Transcribed Image Text:

Let G = (V,E) be a graph. Consider variables xe associated with each edge e E. Let P(G) be the polytope given by: eed(v) e 1 \v V Xe 0 Ve EE We showed in class that if G is bipartite, then all vertices of P(G) are integral by the TUM property of the constraint matrix. Show the converse that if G is not bipartite, then there exists a non integral vertex. Let G = (V,E) be a graph. Consider variables xe associated with each edge e E. Let P(G) be the polytope given by: eed(v) e 1 \v V Xe 0 Ve EE We showed in class that if G is bipartite, then all vertices of P(G) are integral by the TUM property of the constraint matrix. Show the converse that if G is not bipartite, then there exists a non integral vertex.

Answer rating: 100% (QA)

To show the converse we need to prove that if G is not bipartite then there e... View the full answer