Bipartite density of cubic graphs (Q1861239)

The bipartite density is the ratio of the maximum number of edges in a bipartite subgraph to the number of edges in a graph. The authors prove that the bipartite density of a cubic line graph with at least six vertices is equal to 7/9. Further, they prove that the bipartite density of a connected cubic graph is at most \(\frac{4}{7+\lambda_{\min}}\), where \(\lambda_{\min}\) is the smallest eigenvalue of the adjacency matrix of the graph, and they characterize the case of equality in most cases.