Graph Theory/Connectivity

From Wikibooks, the open-content textbooks collection

This book has been created on 19 June 2009, and still is under heavy construction. Content that is added is likely to be moved/deleted/edited significantly in a short amount of time. All wikibookians with knowledge in this subject are welcome to help out. You can remove this tag when the book has become more mature.

Contents 1 Definition of Connectedness 2 Theorems on Connectedness

Whether or not it is possible to traverse a graph from one vertex to another is dependent on how connected a graph is.

[edit] Definition of Connectedness

1. If there is a u-v path in G, then we say that u and v are connected
2. If there is a u-v path for every pair of vertices u and v in G, then we say that G is connected

[edit] Theorems on Connectedness

Theorem: Let G be a graph of order at least 3. If there are distinct vertices u and v in G so that G-u and G-v are both connected, then G is also connected. Proof: to be completed