I know k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k. How is it different from a "maximal" k-degenerate graph? I heard maximal k-degenerate graphs are "upper extremal k-monocore graphs". What's a k-monocore graph?
The difference between k-degenerate graph and maximal k-degenerate graph
graph theory
Best Answer
In general, a "maximal property-$X$ graph" is a graph with property $X$ that has as many edges as possible in the weak sense that adding any edge not already present would destroy property $X$.
For example, a maximal acyclic graph is a tree, a maximal bipartite graph is a complete bipartite graph, and a maximal $k$-colorable graph is a complete $k$-partite graph.
So a maximal $k$-degenerate graph is a graph with the property that if you add any other edge to it, it stops being $k$-degenerate. You don't need to know what a $k$-monocore graph is to understand this definition.
It appears, however, that a $k$-monocore graph is a $k$-degenerate graph with minimum degree $k$. For graphs with at least $k+1$ vertices, we can prove that a maximal $k$-degenerate graph is a $k$-monocore graph:
First, let $G$ be a maximal $k$-degenerate graph and $v_1, v_2, \dots, v_n$ be a vertex ordering such that $v_i$ has at most $k$ edges to $v_{i+1}, \dots, v_n$. (Having such a vertex ordering is equivalent to being $k$-degenerate.) Then the vertices $v_{n-k}, v_{n-k-1}, \dots, v_n$ must form a clique (and therefore have degree $\ge k$), by maximality: any missing edges between them could be added without ruining the vertex ordering. For any other vertex $v_i$, if it had degree less than $k$, we could bring its degree up to $k$ by adding edges to some of the last $k+1$ vertices without ruining the ordering; therefore, by maximality, $G$ has minimum degree at least $k$. In fact, it has minimum degree exactly $k$ because the degree of $v_1$ is $k$.
I don't know what makes $k$-monocore graphs be "upper extremal".