Quantifying non-bipartiteness Suppose I have a graph that is bipartite, except for one edge.  That is, if this one edge were deleted, the graph would be bipartite.  This graph is 'almost' or 'very nearly' bipartite.
A complete graph on many vertices, on the other hand, is extremely non-bipartite, because many edges would need to be deleted to have a bipartite graph.


*

*Does the 'degree of non-bipartiteness' have a name?

*What, if anything, is known about 'nearly bipartite' graphs?

 A: I've read many papers which studied the number of edges that need to be deleted to make a graph bipartite, and none of them had good terminology for it (there is various notation, but nothing that's generally known). On the other hand, there are some interesting results.
Approximately the best thing we can say in general is that if the graph has $m$ edges, we need to delete at most $\frac m2$. (In other words, there is a bipartite graph containing at least half the edges.) This has a probabilistic proof: if we partition the vertex set into two halves randomly and only keep the edges between the two halves, then $\frac m2$ edges are kept in expectation, so there must be some way to keep at least $\frac m2$ edges.
To say more things, we need to add other conditions. One interesting question is: if a graph is triangle-free, how close is it to being bipartite?
We know from Turán's theorem that the most edges a triangle-free graph on $n$ vertices can have is $n^2/4$; the only graph that achieves this is $K_{n/2,n/2}$, which is already bipartite. Brouwer (1981, Some lotto numbers from an extension of Turán's theorem) proves that even if a triangle-free graph has around $n^2/4 - n/2 + 2$ edges, slightly fewer, it must already be bipartite.
For smaller graphs, Erdős, Faudree, Pach, Spencer (1988, How to make a graph bipartite) prove some general bounds: if the triangle-free graph has $n$ vertices and $m$ edges, we can make it bipartite by deleting at most
$$
    \min \left\{ \frac m2 - \frac{2m(2m^2 - n^3)}{n^2(n^2-2m)}, m - \frac{4m^2}{n^2}\right\}
$$
edges. The first part of the $\min$ strengthens the $\frac m2$ claim for general graphs; the second part is good when $m$ is close to $\frac{n^2}{4}$. A slightly weaker version of the second part is that a triangle-free graph with $n^2/4-t$ edges can be made bipartite by deleting $t$ more edges.
Füredi (2015, A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity) proved a generalization of this for $K_{r+1}$-free graphs: if they're $t$ edges away from the maximum number they could have, then they can be made $r$-partite by deleting $t$ more edges.
A: A graph is bipartite if and only if it has no odd-length cycle, so an almost bipartite graph either has exactly one odd cycle, or it has more than one odd cycle and they all share a common edge. 
