Degree (graph theory)

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Handshaking lemma Degree (graph theory)_section_0

Main article: Handshaking lemma Degree (graph theory)_sentence_0

The formula implies that in any undirected graph, the number of vertices with odd degree is even. Degree (graph theory)_sentence_1

This statement (as well as the degree sum formula) is known as the handshaking lemma. Degree (graph theory)_sentence_2

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 (graph theory)_sentence_3

Degree sequence Degree (graph theory)_section_1

The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees; for the above graph it is (5, 3, 3, 2, 2, 1, 0). Degree (graph theory)_sentence_4

The degree sequence is a graph invariant so isomorphic graphs have the same degree sequence. Degree (graph theory)_sentence_5

However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs have the same degree sequence. Degree (graph theory)_sentence_6

The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. Degree (graph theory)_sentence_7

(Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) Degree (graph theory)_sentence_8

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. Degree (graph theory)_sentence_9

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. Degree (graph theory)_sentence_10

The inverse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. Degree (graph theory)_sentence_11

The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a matching, and fill out the remaining even degree counts by self-loops. Degree (graph theory)_sentence_12

The question of whether a given degree sequence can be realized by a simple graph is more challenging. Degree (graph theory)_sentence_13

This problem is also called graph realization problem and can either be solved by the Erdős–Gallai theorem or the Havel–Hakimi algorithm. Degree (graph theory)_sentence_14

The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration. Degree (graph theory)_sentence_15

Special values Degree (graph theory)_section_2

Degree (graph theory)_unordered_list_0

  • A vertex with degree 0 is called an isolated vertex.Degree (graph theory)_item_0_0
  • 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.Degree (graph theory)_item_0_1
  • A vertex with degree n − 1 in a graph on n vertices is called a dominating vertex.Degree (graph theory)_item_0_2

Global properties Degree (graph theory)_section_3

Degree (graph theory)_unordered_list_1

  • 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.Degree (graph theory)_item_1_3
  • 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.Degree (graph theory)_item_1_4
  • 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.Degree (graph theory)_item_1_5
  • 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.Degree (graph theory)_item_1_6
  • A k-degenerate graph is a graph in which each subgraph has a vertex of degree at most k.Degree (graph theory)_item_1_7

See also Degree (graph theory)_section_4

Degree (graph theory)_unordered_list_2

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: (graph theory).