Last time we defined a graph to be "connected" if there were a series of edges connecting any two vertices. But the graph with just one vertex has no edges. Surely we'd like it to be connected, though.
Fix #1: ask instead for a series of vertices.
Fix #2: ask for a series of edges connecting any two different vertices.
Union of sets, intersection, subset.
Def. A decomposition of a graph.
We started proving
Thm. A graph is connected iff it has no nontrivial decompositions.
Proof. => Assume G is connected. If it has a nontrivial decomposition... well, no it doesn't.
Next time: we'll go the other direction, and discuss proofs by contradiction; sections 1.4-1.6 of [FP].
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment