Degree of a vertex
Builds on Neighbourhood
Definition
Let be a graph and let be a vertex of with a finite neighbourhood . The degree of is the number of vertices adjacent to . It is also the number of edges that contain .
Remarks
A vertex of degree is isolated, and a vertex of degree is a leaf. A graph is locally finite when each vertex has finite degree. Each finite graph is locally finite. In a multigraph, the degree counts edges with multiplicity, and a loop counts twice.
Reading path
To understand this page from the ground up, read these 3 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Graph definition
- Neighbourhood definition
- Degree of a vertex definition
Where this leads
16 pages build on this one.
- Euler's theorem on Eulerian circuits
- Degrees along an Eulerian trail
- Every finite tree with at least two vertices has a leaf
- Regular graph
- Maximum degree
- Ore's theorem
- Number of odd-degree vertices is even
- Dirac's theorem on Hamiltonian cycles
- Minimum degree
- Handshaking lemma
- Brooks' theorem
- Laplacian matrix
- Vizing's theorem
- Expander graph
- Strongly regular graph
- Petersen's theorem
Further reading
- Web https://en.wikipedia.org/wiki/Degree_(graph_theory), lead section
About this page
| Tag | 0T0F6CCS9W |
|---|---|
| URI | m2://0T0F6CCS9W |
| Kind | definition |
| Writing | W1 stated |
| MSC | 05C07 |
| Defines | Degree of a vertex |
| Uses | Neighbourhood |
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.