Graph Theory/Connectivity
From Wikibooks, the open-content textbooks collection
Contents |
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
- If there is a u-v path in G, then we say that u and v are connected
- 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