Solution of three problems of Cornuéjols (Q2464157)

A graph is balanced if it is bipartite and every induced cycle has length divisible by four. In 2001, \textit{G. Cornuéjols} proposed in his book [Combinatorial optimization: Packing and covering, CBMS-NSF Regional Conference Series in Applied Mathematics, 74, Philadelphia, SIAM (2001; Zbl 0972.90059)] a number of conjectures. The authors solve three of them about balanced graphs. In particular, they prove Conjecture 9.29 on page 100 of [loc. cit.], which asserts the following: Conjecture (\textit{M. Conforti, G. Cornuéjols, A. Kapoor}, and \textit{K. Vušković} [J. Comb. Theory, Ser. B 81, 243--274 (2001; Zbl 1026.05016)]). Every balanceable bipartite graph that is not regular has a double star cutset.