1
$\begingroup$

I found this problem in a textbook with no answer provided:

Consider a graph G.

Do all subgraphs of G have to be either induced or spanning?


My inclination is that they do not since

(a) An induced subgraph is obtained by deletion of nodes only

(b) A spanning subgraph is obtained by deletion of edges only

Create a subgraph by deletion of one node and one edge. This is neither spanning nor induced.

Is this correct?

$\endgroup$
1
$\begingroup$

Yes, as long as the deleted edge is not incident to the deleted node.

$\endgroup$

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.