Bipartite density

Bipartite density --- двудольная плотность.

Let [math]\displaystyle{ G = (V,E) }[/math] be a simple graph Let [math]\displaystyle{ H }[/math] be any bipartitesubgraph of [math]\displaystyle{ G }[/math] with the maximum number of edges. Then ([math]\displaystyle{ \varepsilon(G) = |E(G)| }[/math]) [math]\displaystyle{ b(G) = \frac{\varepsilon(H)}{\varepsilon(G)} }[/math]

is called the bipartite density of [math]\displaystyle{ G }[/math]. The problem of determining the bipartite density of a graph is NP-complete problem even if [math]\displaystyle{ G }[/math] is cubicand triangle-free