Degree (graph Theory) - Global Properties

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.