# Chapter 5. Degree of a Vertex # Chapter 5. Degree of a Vertex The degree of a vertex measures how many edges meet at that vertex. It is one of the first numerical invariants of a graph. Degree is local: it describes the immediate position of one vertex, rather than the whole graph. Degree appears in nearly every part of graph theory. It is used to count edges, detect isolated vertices, describe regular graphs, prove existence theorems, bound algorithms, and state conditions for paths, cycles, colorings, and connectivity. ## 5.1 Definition Let \(G = (V,E)\) be an undirected graph, and let \(v \in V\). The **degree** of \(v\), written $$ \deg(v), $$ is the number of edges incident with \(v\). If \(G\) is a simple graph, then this is the same as the number of neighbors of \(v\): $$ \deg(v) = |N(v)|. $$ Here \(N(v)\) denotes the neighborhood of \(v\), the set of all vertices adjacent to \(v\). For example, if $$ E = \{\{a,b\}, \{a,c\}, \{a,d\}, \{b,d\}\}, $$ then the degrees are $$ \deg(a)=3, \qquad \deg(b)=2, \qquad \deg(c)=1, \qquad \deg(d)=2. $$ The vertex \(a\) has degree \(3\) because three edges meet at \(a\). ## 5.2 Isolated Vertices and Leaves A vertex of degree \(0\) is called an **isolated vertex**. If $$ \deg(v)=0, $$ then \(v\) has no incident edges and no neighbors. It is separated from the rest of the graph. A vertex of degree \(1\) is called a **leaf** or **pendant vertex**. If $$ \deg(v)=1, $$ then exactly one edge is incident with \(v\). Leaves occur frequently in trees. In a finite tree with at least two vertices, there are always at least two leaves. | Degree | Name | Meaning | |---:|---|---| | \(0\) | Isolated vertex | No incident edges | | \(1\) | Leaf or pendant vertex | Exactly one incident edge | | \(2\) | Internal point on a path or cycle | Two incident edges | | \(n-1\) | Universal vertex in a simple graph of order \(n\) | Adjacent to every other vertex | ## 5.3 Degree in Simple Graphs In a simple graph, each edge joins two distinct vertices, and no two vertices are joined by more than one edge. If \(G\) is a simple graph of order \(n\), then every vertex degree satisfies $$ 0 \leq \deg(v) \leq n-1. $$ The lower bound occurs when \(v\) is isolated. The upper bound occurs when \(v\) is adjacent to every other vertex. A vertex with degree \(n-1\) is called a **universal vertex**. In the complete graph \(K_n\), every vertex is universal, so $$ \deg(v)=n-1 $$ for every vertex \(v\). ## 5.4 Degree in Multigraphs In a multigraph, two vertices may be joined by more than one edge. Degree counts edges with multiplicity. If \(u\) and \(v\) are joined by three parallel edges, then those three edges contribute \(3\) to \(\deg(u)\) and \(3\) to \(\deg(v)\). Thus degree counts incidences, not merely distinct neighbors. For a multigraph, the equality $$ \deg(v)=|N(v)| $$ may fail. A vertex may have one neighbor but several incident edges. For example, suppose \(a\) and \(b\) are joined by three parallel edges. Then $$ N(a)=\{b\}, $$ but $$ \deg(a)=3. $$ ## 5.5 Loops and Degree A loop is an edge whose two endpoints are the same vertex. In an undirected graph, a loop contributes \(2\) to the degree of its vertex. This convention agrees with the idea that each edge has two ends. If both ends lie at the same vertex, both are still counted. For example, suppose \(v\) has one loop and two ordinary incident edges. Then $$ \deg(v)=2+1+1=4. $$ This convention is important because it keeps the degree sum formula valid for graphs with loops. ## 5.6 Degree Sequence The **degree sequence** of a finite graph is the list of degrees of all vertices, usually written in nonincreasing order. If the vertex degrees are $$ 1,3,2,2,0, $$ then the degree sequence is $$ (3,2,2,1,0). $$ The degree sequence is a graph invariant. Isomorphic graphs have the same degree sequence. However, the degree sequence alone does not determine a graph. Two non-isomorphic graphs can have the same degree sequence. For example, many different graphs have degree sequence $$ (2,2,2,2). $$ One such graph is a cycle on four vertices. In larger examples, the same degree sequence may describe several different structures. ## 5.7 Regular Graphs A graph is **regular** if all vertices have the same degree. If every vertex has degree \(r\), the graph is called **\(r\)-regular**. Thus, \(G\) is \(r\)-regular when $$ \deg(v)=r $$ for every \(v \in V(G)\). Examples: | Graph | Regularity | |---|---| | Empty graph on \(n\) vertices | \(0\)-regular | | Cycle \(C_n\) | \(2\)-regular | | Complete graph \(K_n\) | \((n-1)\)-regular | | Complete bipartite graph \(K_{n,n}\) | \(n\)-regular | | Petersen graph | \(3\)-regular | Regular graphs are important because they distribute local connectivity evenly. They occur in algebraic graph theory, finite geometry, coding theory, expanders, network design, and random graph models. ## 5.8 Maximum and Minimum Degree Two standard graph parameters are the maximum degree and the minimum degree. The **maximum degree** of \(G\) is $$ \Delta(G)=\max_{v \in V(G)} \deg(v). $$ The **minimum degree** of \(G\) is $$ \delta(G)=\min_{v \in V(G)} \deg(v). $$ If the degree sequence is $$ (5,4,4,2,2,1), $$ then $$ \Delta(G)=5 $$ and $$ \delta(G)=1. $$ These quantities are useful in bounds. For example, if every vertex has degree at least \(1\), then the graph has no isolated vertices. If every vertex has degree at least \(2\), then a finite graph contains a cycle. ## 5.9 Average Degree The **average degree** of a finite graph is $$ \frac{1}{|V|}\sum_{v \in V}\deg(v). $$ Using the degree sum formula, this becomes $$ \frac{2|E|}{|V|}. $$ Thus the average degree measures edge density from the viewpoint of vertices. If a graph has \(n\) vertices and \(m\) edges, its average degree is $$ \frac{2m}{n}. $$ For example, if \(n=10\) and \(m=15\), then the average degree is $$ \frac{2\cdot 15}{10}=3. $$ The average degree may be noninteger, even though every individual degree is an integer. ## 5.10 The Degree Sum Formula For every finite undirected graph, $$ \sum_{v \in V(G)} \deg(v) = 2|E(G)|. $$ This identity is called the **degree sum formula** or the **handshaking lemma**. Each edge has two ends, so each edge contributes \(2\) to the total sum of degrees. ### Proof Count incidences between vertices and edges. First count by vertices. A vertex \(v\) contributes \(\deg(v)\) incidences. Summing over all vertices gives $$ \sum_{v \in V(G)} \deg(v). $$ Now count by edges. Each edge has two ends, so each edge contributes \(2\) incidences. Since there are \(|E(G)|\) edges, the number of incidences is $$ 2|E(G)|. $$ Both expressions count the same set of incidences. Therefore $$ \sum_{v \in V(G)} \deg(v) = 2|E(G)|. $$ ## 5.11 Odd Degree Vertices A vertex is called **odd** if its degree is odd. It is called **even** if its degree is even. The handshaking lemma implies that the number of odd degree vertices in a finite undirected graph is even. ### Proof The degree sum is $$ \sum_{v \in V(G)} \deg(v)=2|E(G)|. $$ The right side is even. Therefore the sum of all degrees is even. Even degree vertices contribute even numbers to the sum. Odd degree vertices contribute odd numbers. A sum of integers is even only when it contains an even number of odd summands. Hence the number of vertices of odd degree is even. This result is often used to prove impossibility. For example, no graph can have exactly one vertex of odd degree. ## 5.12 Degree and Edge Counting The degree sum formula gives a practical way to count edges when the degrees are known. Suppose a graph has degree sequence $$ (4,4,3,3,2,2). $$ The sum of degrees is $$ 4+4+3+3+2+2=18. $$ Therefore $$ 2|E|=18, $$ so $$ |E|=9. $$ A sequence of integers can be the degree sequence of a graph only if its sum is even. This condition is necessary. It is not sufficient. More conditions are required to characterize graphical sequences. ## 5.13 Degree in Directed Graphs In a directed graph, degree splits into two quantities. The **out-degree** of a vertex \(v\), written $$ \deg^+(v), $$ is the number of arcs leaving \(v\). The **in-degree** of \(v\), written $$ \deg^-(v), $$ is the number of arcs entering \(v\). If $$ A = \{(a,b), (a,c), (d,a), (c,a)\}, $$ then $$ \deg^+(a)=2 $$ and $$ \deg^-(a)=2. $$ Every directed edge leaves one vertex and enters one vertex. Therefore $$ \sum_{v \in V}\deg^+(v) = \sum_{v \in V}\deg^-(v) = |A|. $$ This is the directed analogue of the handshaking lemma. ## 5.14 Degree and Local Structure Degree gives local information, but it does not fully determine global structure. A vertex of high degree has many immediate neighbors. It may act as a hub. A vertex of low degree has few immediate connections. It may be peripheral. However, degree alone cannot tell whether the graph is connected, planar, bipartite, or contains a cycle. Two graphs may have the same degree sequence but different global behavior. For example, a graph with degree sequence $$ (2,2,2,2,2,2) $$ could be one cycle of length \(6\), or two disjoint cycles of length \(3\). Both graphs have the same degree sequence, but one is connected and the other is disconnected. ## 5.15 Degree Bounds Degree often gives simple but useful bounds. If \(G\) is a simple graph with \(n\) vertices, then $$ \sum_{v \in V(G)} \deg(v) \leq n(n-1). $$ This follows from $$ \deg(v) \leq n-1 $$ for every vertex \(v\). By the degree sum formula, $$ 2|E(G)| \leq n(n-1), $$ so $$ |E(G)| \leq \frac{n(n-1)}{2}. $$ Equality holds exactly for the complete graph \(K_n\). ## 5.16 Example Let $$ V=\{a,b,c,d,e,f\} $$ and $$ E= \{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{d,e\},\{e,f\}\}. $$ The neighborhoods are $$ N(a)=\{b,c,d\}, $$ $$ N(b)=\{a,c\}, $$ $$ N(c)=\{a,b\}, $$ $$ N(d)=\{a,e\}, $$ $$ N(e)=\{d,f\}, $$ $$ N(f)=\{e\}. $$ The degrees are $$ \deg(a)=3, \quad \deg(b)=2, \quad \deg(c)=2, \quad \deg(d)=2, \quad \deg(e)=2, \quad \deg(f)=1. $$ The degree sequence is $$ (3,2,2,2,2,1). $$ The sum of degrees is $$ 3+2+2+2+2+1=12. $$ Therefore $$ |E|=\frac{12}{2}=6, $$ which agrees with the listed edge set. There are two odd degree vertices: \(a\) and \(f\). This agrees with the theorem that the number of odd degree vertices is even. ## 5.17 Summary The degree of a vertex is the number of incident edges. In a simple graph, this equals the number of neighbors. In a multigraph, parallel edges are counted with multiplicity. In an undirected graph with loops, each loop contributes \(2\) to the degree of its vertex. The central identity is $$ \sum_{v \in V(G)} \deg(v)=2|E(G)|. $$ It follows that the sum of degrees is even and that the number of odd degree vertices is even. Degree sequences, regular graphs, minimum degree, maximum degree, and average degree provide compact numerical information about graph structure.