# Graphs constructed by subsequently adding small degree vertices . Generalisation of trees?

Definition. For $k\ge 1$ we call a graph $k$-constructible if it can be obtained from the empty graph by subsequently adding new vertices and connecting them to at most $k$ previously existing vertices.

First two elementary observation:

• A graph is $k$-constructible if and only if it is $k$-destructible in the sense that it can be transformed into the empty graph by subsequently removing vertices of degree at most $k$ and its adjacent edges.
• A graph is $k$-destructible if and only if it is so greedily. By this I mean that one can subsequently remove any vertex of degree at most $k$ to obtain the empty graph.
• A graph is $1$-constructible if and only if it is a forest. In other words, a graph is $1$-constructible if it contains no cycles, i.e., if it does not contain $K_3$ as a minor.

Questions.

1. For $k>1$ do these classes of graphs have common names?
2. Is there an alternative more directly verifiable condition to figure out whether a graph is $k$-constructible?

I would also be very happy to know answers to these questions for $k=2$ only.

It is obvious that a graph containing $K_4$ as a subgraph cannot be $2$-constructible. So I briefly thought whether graphs might be $2$-constructible if and only if they do not contain $K_4$ as a minor. But this turns out to be wrong since a $K_4$ with one edge subdivided into two edges is $2$-constructible.

• Thanks for the reference! If you post it as an answer, I'll accept it Oct 19, 2017 at 6:52

These are called $k$-degenerate graphs in the graph theory literature.