Algorithm for finding a particular spanning bipartite subgraph This is an exercise from a book (Bondy/Murty):

a) Deduce from Theorem 2.4 that every loopless graph $G$ contains a spanning bipartite subgraph $F$ with $e(F)\geq\frac{1}{2}e(G)$.
b) Describe an algorithm for finding such a subgraph by first arranging the vertices in a linear order and then assigning them, one by one, to either $X$ or $Y$, using a simple rule.

Here is Theorem 2.4 mentioned above:

Every loopless graph $G$ contains a spanning bipartite subgraph $F$ such that $d_F(v)\geq\frac{1}{2}d_G(v)$ for all $v\in V$.

Part (a) of the above exercise is easy, but I'm having a hard time with part (b). First of all I don't think linear order is even defined in the book, and the only order that I can think of is the degrees of the vertices, but that seems useless. Does anyone have any ideas?
 A: By "linear order", they just mean to assign a total order on the vertex set.  The simplest way to do this, is to label the vertices $[n]:=\{1,2,\ldots,n\}$, where $n$ is the number of vertices.  The word "linear" here is meant to conjure up the idea that the vertices are placed along a line: so each edge has a unique up endpoint and a unique down endpoint.
Let $N(v)$ denote the neighbourhood of $v \in [n]$.  Let $D(v)$ denote the down neighbourhood of $v \in [n]$, i.e., $$D(v)=\{u \in N(v):u<v\}.$$  The number of edges in $G$ is thus $$|E(G)|=\sum_{v \in [n]} |D(v)|$$ since each edge has a unique up endpoint.
We assign the vertices to $X$ or $Y$ using a greedy algorithm.


*

*Start with $X=Y=\emptyset$.

*For $v=1,2,\ldots,n$ (in order), we add


*

*$v$ to $X$ if $|D(v) \cap Y| \geq |D(v) \cap X|$ and

*$v$ to $Y$ otherwise.



In this way, when processing vertex $v$, we ensure at least $\tfrac{1}{2} |D(v)|$ edges are $X$-to-$Y$ edges.  The total number of $X$-to-$Y$ edges will thus be at least $$\sum_{v \in [n]} \tfrac{1}{2} |D(v)|=\tfrac{1}{2}|E(G)|.$$
