Show $2$-degenerate graphs are subgraphs of $2$-degenerate plane bipartite graphs

130 Views Asked by At

I am trying to prove or find a counterexample for the following claim: any planar $2$-degenerate graph is a subgraph of a $2$-degenerate plane bipartite graph (a planar graph whose faces are all $4$-gons). It is known that $2$-degenerate bipartite graphs can be obtained from $C_4$ by inserting a vertex of degree 2 (and thus two new edges at the same time). My idea was to argue that one could take any $2$-degenerate planar graph and add edges and vertices in such manner to obtain a plane bipartite graph, but I am completely lacking the argument of how to make sure that 1) this is in fact always possible, and 2) the resulting plane graph is in fact bipartite and 2-degenerate.

$2$-degenerate graphs are graphs such that every subgraph of a $2$-degenerate graph contains a vertex of degree $2$.