Crossing Planar Graphs Let $G$ be a non-null simple graph, drawn in the plane with crossings , so that every edge crosses at most $k$ other edges. Show that $m \leq 3(k+1)n$.
I think one way to prove the statement directly follows if you can partition the graph into (k+1) planar graphs. I am just unclear on why that is doable. Any help would be greatly appreciated.
 A: I will use following lemma (it is easy to prove by induction on the number of vertices,
let me know if you don't succeed, then I'll add the proof):
Let $G$ be a graph with $n$ vertices and $\Delta(G)=k\geq 1$.
Then there is an independent set $S$ such that $\Delta(G-S)<k$.
For the proof of your problem we use induction on $k$:
Induction base: $k=0$. Then $m\leq 3n-6\leq 3n=3(k+1)n$.
Induction step: We assume $k>0$ and the statement proven for values smaller than $k$.
We consider the "edge graph" $H$, whose vertices are the edges of $G$ (so $|H|=m$)
and where two vertices of $H$ are adjacent if and only if the corresponding edges in $G$ cross.
$H$ is a graph with $\Delta(H)\leq k$, so we can use the lemma to find an independent set $S$
such that $\Delta(H-S)\leq k-1$.
Translating this back to $G$ we find that $H-S$ corresponds to a subgraph $G'$ of $G$ such that every
edge of $G'$ crosses at most $k-1$ other edges, so by the induction hypothesis $e(G')\leq 3kn$.
Since $S$ was an independent set it corresponds to a subgraph $G''$ of $G$ whose edges do not cross,
so $G''$ has at most $3n$ edges (this was the induction base).
We conclude that $G$ has at most $3kn+3n=3(k+1)n$ edges.
Note that a minor modification of this proof shows the slightly stronger result that $m\leq(k+1)(3n-6)$.
