Connected graph
Builds on Reachability
Definition
A graph is connected if its vertex set is nonempty and any two vertices of are reachable from each other.
Remarks
The empty graph, with no vertices, is not connected under this convention. Some authors call it connected. A graph is connected if and only if it has exactly one connected component. The cycle graphs, the path graphs and the trees are connected.
Reading path
To understand this page from the ground up, read these 4 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Graph definition
- Walk definition
- Reachability definition
- Connected graph definition
Where this leads
25 pages build on this one.
- Euler's theorem on Eulerian circuits
- K5 and K3,3 are not planar
- Every connected graph has a spanning tree
- Unique paths in trees
- Forest
- Prüfer sequence
- Trees are bipartite
- Rooted tree
- Spanning tree
- Every finite tree with at least two vertices has a leaf
- Kuratowski's theorem
- Cayley's formula
- Tree
- Edge bound for planar graphs
- A tree on n vertices has n − 1 edges
- Euler's formula for planar graphs
- Minimum spanning tree
- Crossing number inequality
- Net of a polyhedron
- Unit distance problem
- Treewidth
- Cheeger constant
- k-vertex-connected graph
- Graph minor
- Kruskal's tree theorem
Further reading
- Web https://en.wikipedia.org/wiki/Connectivity_(graph_theory), Connected vertices and graphs
About this page
| Tag | 0FFAYNMAJZ |
|---|---|
| URI | m2://0FFAYNMAJZ |
| Kind | definition |
| Writing | W1 stated |
| MSC | 05C40 |
| Defines | Connected graph |
| Uses | Reachability |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge instance_of in: one example (0 of 1)
- edge not_instance_of in: one non-example that fails one clause (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.