AI Tutor
Back to Definitions

Exercise 10

Avg difficulty 2.5

Decide whether the statements below about subgraphs are true or false. For those that are true, briefly explain why (1 or 2 sentences). For any that are false, give a counterexample.

  1. Any subgraph of a complete graph is also complete.

  2. Any induced subgraph of a complete graph is also complete.

  3. Any subgraph of a bipartite graph is bipartite.

  4. Any subgraph of a tree is a tree.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), §5.1 Definitions, Exercise 10

AI Tutor

Adapted from Discrete Mathematics: An Open Introduction © 2013–2019 Oscar Levin. Licensed under CC BY-SA 4.0. Source: Discrete Mathematics: An Open Introduction. Imported at revision 1e2e26b.