Largest bipartite subgraphs in triangle‐free graphs with maximum degree three
J. Adrian Bondy, Stephen C. Locke · Journal of Graph Theory · 1986
Abstract Let G be a triangle‐free, loopless graph with maximum degree three. We display a polynomial algorithm which returns a bipartite subgraph of G containing at least ⅘ of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3‐regular, triangle‐free, loopless, connected graphs for which no bipartite subgraph has more than this proportion.