Question

# Suppose G is a simple, nonconnected graph with n vertices that is maximal with respect to...

Suppose G is a simple, nonconnected graph with n vertices that is maximal with respect to these properties. That is, if you tried to make a larger graph in which G is a subgraph, this larger graph will lose at least one of the properties (a) simple, (b) nonconnected, or (c) has n vertices.

What does being maximal with respect to these properties imply about G?G? That is, what further properties must GG possess because of this assumption?

In this activity you hopefully decided that a graph as described in the activity must:

1. have exactly two connected components; and
2. each connected component must be a complete graph.

Prove these two statements.

Notes:

• Write a separate proof for each of the two statements.
• Your proofs should be general proofs; they should not rely on examples.
• Be aware that there isn't just one unique graph G as described in the activity for each value of n. In fact, for each n≥4 there will be n/2 different versions of such maximal simple nonconnected graphs (rounding n/2 down in case n is odd), and the different versions will have different numbers of edges while still having the same number of vertices.

Hint: For each of the two proofs, you might consider arguing by contrapositive or by contradiction.

#### Earn Coins

Coins can be redeemed for fabulous gifts.