<p>Yes. By Proposition 2.3 of [1], all elementary fractional extreme points of the LP correspond to subgraphs that contain odd cycles, and therefore if the graph contains no odd cycles, the LP has an optimal solution that takes on only integer values.</p>

<p>[1] G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. Mathematical Programming, 6:48–61, 1974.</p>

CC BY-SA 4.0
2020-01-15T11:04:25.990Z
2020-01-15T11:04:25.990Z
Laakeri
<p>Suppose we have a graph <strong>G</strong> without odd cycles. Consider the minimum vertex cover problem of <strong>G</strong> formulated as a linear programming problem, that is for each vertex <span class="math-container">$v_{i}$</span> we have the variable <span class="math-container">$x_{i}$</span>, for each edge <span class="math-container">$v_{i}v_{j}$</span> we have the constraint <span class="math-container">$x_{i}+x_{j}\geq1$</span>, for each variable we have <span class="math-container">$0\leq x_{i}\leq1$</span> and we have the objective function <span class="math-container">$\min\sum\limits_{i}{x_{i}}$</span>. Note that it is NOT an integer linear programming problem.</p>

<p>Is true that the value of the objective function is the cardinality of the minimum vertex cover of <strong>G</strong>, that is it is the number of verices of the minimum vertex cover of <strong>G</strong>?</p>

<graph-theory><graph-algorithms>
Minimum vertex cover and odd cycles
Mario Giambarioli
# Minimum vertex cover and odd cycles

(Asked by: username_0 on 2020-01-15)

Suppose we have a graph **G** without odd cycles. Consider the minimum vertex cover problem of **G** formulated as a linear programming problem, that is for each vertex $v\_{i}$ we have the variable $x\_{i}$, for each edge $v\_{i}v\_{j}$ we have the constraint $x\_{i}+x\_{j}\geq1$, for each variable we have $0\leq x\_{i}\leq1$ and we have the objective function $\min\sum\limits\_{i}{x\_{i}}$. Note that it is NOT an integer linear programming problem.

Is true that the value of the objective function is the cardinality of the minimum vertex cover of **G**, that is it is the number of verices of the minimum vertex cover of **G**?

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2020-01-15. Score: 2 | Accepted answer

Yes. By Proposition 2.3 of [1], all elementary fractional extreme points of the LP correspond to subgraphs that contain odd cycles, and therefore if the graph contains no odd cycles, the LP has an optimal solution that takes on only integer values.

[1] G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. Mathematical Programming, 6:48–61, 1974.


---

