Word Count : 1445

---

The handshaking theorem—often called the handshaking lemma—is a foundational result in graph theory that connects local information at vertices to a global count of edges. In its most familiar form for an undirected finite graph $G=(V,E)$, it states that the sum of the degrees of all vertices equals twice the number of edges: $\sum_{v\in V}\deg(v)=2|E|$. Intuitively, every handshake involves two hands; likewise, every edge is incident with exactly two (not necessarily distinct, if loops are allowed) endpoints, so it contributes $2$ to the total degree count. This deceptively simple statement has numerous important corollaries and applications, ranging from parity constraints on degree sequences to quick consistency checks in modeling networks. To define terms precisely, consider an undirected graph $G=(V,E)$ where $V$ is a finite set of vertices and $E$ is a finite multiset of unordered pairs of vertices. In a simple graph, pairs are distinct and no loops are present; in a multigraph, multiple edges between the same pair may occur; in a pseudograph, loops $\{v,v\}$ are also allowed. For a vertex $v$, the degree $\deg(v)$ equals the number of edges incident with $v$. By convention, a loop contributes $2$ to the degree of its vertex, since the loop touches $v$ twice. A clean proof uses double counting. Consider the set $I$ of incidences between vertices and edges: $$ I=\{(v,e)\in V\times E : \text{edge } e \text{ is incident with vertex } v\}. $$ We count $|I|$ in two ways. First, fix a vertex $v$. The number of incidences involving $v$ equals $\deg(v)$. Summing over all vertices yields $|I|=\sum_{v\in V}\deg(v)$. Second, fix an edge $e$. For a simple or multigraph without loops, each edge has exactly two incidences (with its two endpoints), so $|I|=2|E|$. If loops are allowed, each loop has two incidences with its unique endpoint, so this statement still holds: every edge, loop or not, contributes $2$ incidences. Equating the two counts gives the handshaking theorem $\sum_{v\in V}\deg(v)=2|E|$. An alternative proof employs the adjacency matrix $A$ of a simple graph with vertices $v_1,\dots,v_n$. The $i$th row-sum of $A$ equals $\deg(v_i)$. Because $A$ is symmetric for an undirected graph, the sum of all entries is $2|E|$ (each edge $\{v_i,v_j\}$ contributes ___ _________ __________ __________ ______ _______ __________ ______ ______.
______ _____ _______ ___ __________ ________ ________.
___ _______ ______ ________ ________ ____ _____ ______ _______ ________ _________.
_______ _____ _____ ___ _______.
______ ______ ______ _____ _______ _____ __________ _____ _____.
________ ___ _______ _____ _________ _____ _____ __________ _______.
_________ ______ ____ ________ _____ ________ _________ ________ _________ __________.
________ _________ ____ _____ ________.
____ ______ ___ _______ ___.
_______ _________ _____ ____ ________ _________.
________ _____ ___ __________ _________.
_______ ________ __________ _________ ______ ________ _____ ___ ____ ______.
_________ _____ _______ __________ _________ _________ ________ ___ _______.
________ ________ ______ ______ _____ ________ ___ ___ __________ ____.
____ ____ ______ __________ ____ ____ ______ ___.
_______ ___ ____ _____ _____.
___ _____ ______ __________ _______ ____ _______ _______ _________ _________.
______ ________ __________ _______ __________.
____ _____ ________ ______ _____ ____ _______ ______ _______ _________ _______ _____.
__________ ________ ______ ________ ___ _______.
_________ _____ _____ _______ __________ ______.
_____ ____ ______ ______ _______ _________ _____ __________ __________ ___ _____ ____.
_________ _________ _____ ___ _________ ______ ________.
________ ___ ________ __________ ________.
_____ _______ ____ ____ ____ ___ ___ ___ __________ _________ ___.
________ _______ __________ ____ _________ _______ ___ ______.
____ _______ _______ _______ _______ _______ ___.
______ _____ _________ ________ ____ __________ ______ ___ ________.
__________ ____ ___ _________ _____.
_________ __________ _____ _____ _________ _________ ____ ________ _______ _________ ________.
____ _______ _____ ___ ____ __________.
_________ ____ ________ ______ ______ ______ ________ ______ ____ _______.
____ _____ _____ __________ _______ _________.
__________ __________ ___ ________ ____ ___ _______ ___ ___ __________ ______.
___ ________ ________ ___ ________ ____ __________ ___ ________.
______ _______ _________ _____ ____ _______ _________ ___ __________.
_______ _____ ______ _____ ________ ______ ________ ______ _______ ______ ________.
__________ ________ _____ _______ _______ ________ ___ _______ _________.
_______ _______ _________ ________ _____.
_________ ________ ___ ____ ____ ________ ____ ______ _______ ____.
_____ ___ ___ __________ _________.
__________ _________ ____ ________ ___.
_________ ____ ________ ________ ___ __________ ______.
___ _____ ___ ______ ______.
_______ ____ ___ _____ _____ _________.
_____ ___ ______ ______ _______.
________ ___ _____ _______ _______ _______ ________ ____ ______.
__________ _________ ______ _________ _____ ____ _____ ________ ______ __________.
__________ ____ __________ ________ __________ ______ ___ ___ _________ _____.
_____ ___ _______ _________ ________ _____ _________.
______ ______ _____ ____ __________.
____ ______ ______ ________ _____ ___ ____ ___.
_____ ___ ___ __________ ___.
______ _____ ____ ___ _____ _____ _________ ______ _________ __________.
______ ________ ___ _________ _____ _________ ____ _______.
____ _______ _______ _____ ________.
___ ___ __________ ______ ____.
_________ ___ __________ _____ ___ ___ ______ __________ __________ __________.
______ __________ _______ ______ ________ _______ _________.
______ ______ _________ ____ ________ _______.
_______ ______ _______ _________ __________ ___ ____ ____.
_______ _____ _______ _________ ___ ________ ____ _________ _______.
______ _________ __________ _________ ____ ____ ___ ______ ____ _________ __________.
__________ _______ ______ ___ _________ _________ ______ ________.
______ ____ _______ ________ ______ ____ _______.
__________ ____ ____ ____ ___ ____ __________.
________ ___ _____ __________ ____ ____ _________.
_____ ______ _______ _______ __________.
________ ________ ______ ___ ______ ___ _____ _______ _____ __________ ___ ____.
________ _______ __________ _____ __________ _________ ________ _______ _________ _______.
____ _________ ____ ___ ________ _________.
___ _________ ________ ______ ___ _____ _________ ______ ______ __________ _______.
___ ______ ___ _______ _____ ________ _____ ______.
___ ___ _______ ___ _______.
____ ________ _______ ______ _____ __________ ______ ___ _______ _______.
______ _________ _________ _______ _______ _________.
_____ ___ _______ ________ __________ ________ _________ _________.
_______ _____ ____ _______ __________ ________ _______.
___ __________ ________ __________ ______ _______.
______ __________ _____ _______ ______ __________.
___ _____ ______ ___ ___ _________ ________ _______ ____ __________ _____ ________.
__________ __________ _____ __________ ______ _______ _____ ___ _____.
_______ ________ ____ _____ _______ ________ ____ _____ _______.
_______ ________ __________ ___ __________.
_______ _______ _________ _________ __________ ______ ____ __________ ____ __________ ___ ________.
___ ______ ____ _____ ___ _______.
__________ _______ _____ ______ _____ ________ _________ ________ __________ ______ ________.
_____ ________ ____ _____ ___ _____ __________ __________.
_________ ______ _______ _____ _________ _________ ___ _________ _____.
_______ ____ _______ ___ _____ ____.
_________ _______ ______ ____ ________.
___ _______ __________ _______ _________ _______ ____.
________ _____ _____ _________ ________.
________ ________ __________ __________ ____ _____.
_____ ________ __________ ___ _______ ______ ____ ______ ____.
____ __________ _________ _________ ____ ________ __________ ____ _______ _________.
___ _________ ___ _______ __________ _______ _____ __________ _____.
____ ____ ________ _______ ______ ___ _______ __________ ________.
_________ _________ ____ ______ ___ ______.
____ ____ ___ ___ __________ ______ ______.
_________ _____ ________ _________ ____ ________ ____ ____.
_________ _________ _______ ______ ________ _____ _________ _____ _______ ______ ________.
___ ___ _________ ______ _________ ____ ________ _____ _____ _____ ______.
________ ______ _______ _________ ________ __________.
____ ______ ___ ___ ____ __________ ______ _____ __________ ____.
________ _________ _______ ________ __________ ________ _______ __________ ______ ___.
____ __________ _____ ________ ____ ______ ____ ________ ______ _____.
________ ___ _______ _______ _________ ____ _______.
_________ ___ _________ _______ ___ ________.
____ ____ _____ ______ _____.
___ __________ _________ _______ _______ ______ __________ ___ _________ _______.
__________ ________ _________ ________ _____ ______ _______ _________ ___ _______.
________ _________ ____ _________ ______ ______ _____.
_________ __________ _____ _______ _____ _____ __________ ________ ____ ____.
______ _______ _________ ___ ____ __________ ____ _____ ____.
_______ _____ ________ ________ ___.
_____ _____ _________ ____ _____ _______ ____ ____ _________ _______.
_______ _____ ________ _______ _____ ___ _____ ________ __________ ______ _____.
_____ ___ _______ ____ ___ ______ _______ ____ __________.
____ _____ _________ ______ ________ ______ _______ ______ _____.
___ ____ ________ ___ ____ __________ _________ ________ ______ _____ _____ ______.
___ _____ __________ _________ ____ ______ _____ __________ _______ ______ ____ ______.
___ _________ ____ _____ ___ ____ _________ ________ _______ _______.
__________ _________ ______ _____ _____ _______ ______.
___ _______ _____ _______ _______ _____ ___ __________.
____ ________ _______ _______ _____ ______ ____.
_________ ___ ___ ______ __________ _________ __________.
_________ _____ _______ ____ ____ _____ _____ ___.
_____ ________ ______ ________ _________ _____ ___ ___ ________.
_____ ______ ___ __________ _________ ________ ________ __________ ________ _________ ____.
_____ ____ _____ __________ ________ ________ ________ _____ ___ _________ _________ _________.
____ _____ ________ _______ ____ ____ _____ ______ _______.
_________ _______ ________ _____ __________.
________ _______ ____ ________ __________ ____ ____ ______ ______ ____ ____ _____.
______ ___ ____.
Get Full Answer on WhatsApp