Global Properties
- If each vertex of the graph has the same degree k the graph is called a k-regular graph and the graph itself is said to have degree k. Similarly, a bipartite graph in which every two vertices on the same side of the bipartition as each other have the same degree is called a biregular graph.
- An undirected, connected graph has an Eulerian path if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit.
- A directed graph is a pseudoforest if and only if every vertex has outdegree at most 1. A functional graph is a special case of a pseudoforest in which every vertex has outdegree exactly 1.
- By Brooks' theorem, any graph other than a clique or an odd cycle has chromatic number at most Δ, and by Vizing's theorem any graph has chromatic index at most Δ + 1.
- A k-degenerate graph is a graph in which each subgraph has a vertex of degree at most k.
Read more about this topic: Degree (graph Theory)
Famous quotes containing the words global and/or properties:
“Much of what Mr. Wallace calls his global thinking is, no matter how you slice it, still “globaloney.” Mr. Wallace’s warp of sense and his woof of nonsense is very tricky cloth out of which to cut the pattern of a post-war world.”
—Clare Boothe Luce (1903–1987)
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)