2
$\begingroup$

A subgraph is called spanning when it includes all of the vertices of the given graph.

Is there a term for a subgraph which includes all the edges of a graph?

Thanks.

$\endgroup$
7
$\begingroup$

If the subgraph includes all edges of the original graph, then it also includes all its vertices, except maybe some with degree $0$.

The minimal such subgraph is the graph in which all $0$-degree vertices were removed. It is called the $1$-core of the graph, a very special case of $k$-core.

$\endgroup$
2
  • 1
    $\begingroup$ Why do you have to remove all the vertices of degree 0? If you only remove some of the vertices of degree 0 then it still contains all the edges. $\endgroup$ Jan 14 at 3:41
  • 1
    $\begingroup$ Indeed! I thought we were talking of the minimal such subgraph, but this is not in the question. The original graph itself actually is one such subgraph. I edited the answer to make this clear, thanks. $\endgroup$ Jan 14 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.