 Degree (graph theory)

In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.^{[1]} The degree of a vertex v is denoted deg(v). The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph, denoted by δ(G), are the maximum and minimum degree of its vertices. In the graph on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, all degrees are the same, and so we can speak of the degree of the graph.
Contents
Handshaking lemma
Main article: handshaking lemmaThe degree sum formula states that, given a graph G = (V,E),
The formula implies that in any graph, the number of vertices with odd degree is even. This statement (as well as the degree sum formula) is known as the handshaking lemma. The latter name comes from a popular mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even.
Degree sequence
The degree sequence of an undirected graph is the nonincreasing sequence of its vertex degrees;^{[2]} for the above graph it is (5, 3, 3, 2, 2, 1, 0). The degree sequence is a graph invariant so isomorphic graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, nonisomorphic graphs have the same degree sequence.
The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given nonincreasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence.
The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration.
As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a graph. The construction of such a graph is simple: connect odd vertices in pairs, and fill with selfloops.
Often one wishes to search for simple graphs, making the degree sequence problem more challenging. Obviously the sequence (8, 4) is not the degree sequence of a simple graph, since we would have the contradiction Δ(G) > (number of vertices − 1). The sequence (3, 3, 3, 1) is also not the degree sequence of a simple graph, but in this case the reason is less obvious. Finding general criteria for degree sequences of simple graphs is a classical problem; solutions have been offered by Erdős and Gallai (1960), V. J. Havel (1955) and S. L. Hakimi (1961), S. A. Choudum and Sierksma et al. (1991).
For example, the Erdős–Gallai theorem states that a nonincreasing sequence of n numbers d_{i} (for i = 1,...,n) is the degree sequence of a simple graph if and only if the sum of the sequence is even and
Havel and Hakimi proved that (d_{1}, d_{2}, ..., d_{n}) is a degree sequence of a simple graph if and only if (d_{2} − 1, d_{3} − 1, ..., d_{d1+1} − 1, d_{d1+2}, d_{d1+3}, ..., d_{n}) is. This fact leads to a simple algorithm (the HavelHakimi algorithm) for realizing a simple graph with a given realizable degree sequence: Begin with a graph with no edges. Maintain a list of vertices whose degree requirement has not yet been met in nonincreasing order of residual degree requirement. Connect the first vertex to the next d_{1} vertices in this list, and then remove it from the list. Resort the list and repeat until all degree requirements are met.
Special values
 A vertex with degree 0 is called an isolated vertex.
 A vertex with degree 1 is called a leaf vertex or end vertex, and the edge incident with that vertex is called a pendant edge. In the graph on the right, {3,5} is a pendant edge. This terminology is common in the study of trees in graph theory and especially trees as data structures.
Global properties
 If each vertex of the graph has the same degree k the graph is called a kregular graph and the graph itself is said to have degree k.
 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 kdegenerate graph is a graph in which each subgraph has a vertex of degree at most k.
See also
 Indegree, outdegree for digraphs
 Degree distribution
Notes
References
 Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: SpringerVerlag, ISBN 9783540261834, http://www.math.unihamburg.de/home/diestel/books/graph.theory/.
 G. Sierksma and H. Hoogeveen, "Seven criteria for integer sequences being graphic, " Journal of Graph Theory 15, No. 2 (1991) 223–231.
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… … Universalium
Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Degeneracy (graph theory) — In graph theory, a k degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph s edges. The degeneracy of a graph is the smallest… … Wikipedia
Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… … Wikipedia
Connectivity (graph theory) — In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… … Wikipedia
Loop (graph theory) — In graph theory, a loop (also called a self loop) is an edge that connects a vertex to itself. A simple graph contains no loops.Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow the presence of… … Wikipedia
Vertex (graph theory) — For other uses, see Vertex (disambiguation). A graph with 6 vertices and 7 edges where the vertex number 6 on the far left is a leaf vertex or a pendant vertex In graph theory, a vertex (plural vertices) or node is the fundamental unit out of… … Wikipedia
Tree (graph theory) — Trees A labeled tree with 6 vertices and 5 edges Vertices v Edges v 1 Chromatic number … Wikipedia
Cage (graph theory) — In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.Formally, an ( r , g ) graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest… … Wikipedia
Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue … Wikipedia