Degree of a Vertex

Graph Theory · Axiom Academy

Understanding vertex degree and its fundamental role in graph theory The degree of a vertex v, denoted deg(v), is the number of edges incident to v. An edge is incident to a vertex if the vertex is one of the edge's endpoints. A loop is an edge that connects a vertex to itself. In degree calculations, a loop contributes 2 to the degree of its vertex because both "ends" of the edge are incident to the same vertex. Minimum degree δ(G) : The smallest degree among all vertices Maximum degree Δ(G) : The largest degree among all vertices These values provide bounds on the connectivity of the graph. A graph is called regular if all vertices have the same degree. If every vertex has degree k, we call it a k-regular graph . A cycle C n is 2-regular (every vertex has degree 2) A complete graph K n is (n-1)-regular The vertices of a cube form a 3-regular graph The degree sequence of a graph is the list of vertex degrees, typically written in non-increasing order (largest to smallest). The degree sequence provides a "fingerprint" of the graph's structure. However, different graphs can have the same degree sequence!

This is the written version of the interactive lesson above. See the full Graph Theory course.