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. _______ ___ ________ __________ ________ _________ ______ ______.
________ _______ ______ _________ ________.
___ _________ __________ ________ _________ ____ ________ _______ _______ ____ _______.
______ _____ _________ _____ _________ _____ _________ _____ _________ ___ ___.
_________ ___ _____ ______ _______.
________ _____ ________ ________ _________ ____ __________ _______ __________ ________ ______ ____.
__________ _______ __________ ___ __________ ________ __________ ___ ______ ______.
___ _______ ________ ___ ____.
_______ ___ _____ _________ ___ _______ ____ ___ _____.
_______ ___ __________ __________ ________ _____ _____.
________ __________ ____ ________ __________ _____ _________ ___ ______.
_____ ________ _________ __________ _____ ____.
______ ______ ____ _____ ____ ___ ______ _______ _______.
____ ___ __________ ____ ____ _______.
______ _______ ________ __________ ______.
___ _______ _____ ______ _______ _____ ________ ___.
_______ ______ _________ _______ ________ ____ _____ __________ ____ _______ _______ ___.
___ ____ ________ ____ __________ _______ ______ __________ _________ ______ ____.
______ ____ __________ _______ ____ ______ _________.
_____ __________ ___ ____ ________.
________ ___ ________ _______ ________ ___ ________ ________ _________.
__________ ___ ____ ____ _______ _______ __________.
___ ________ ________ _____ _______ ______ ________ _____ ______ ____.
____ _____ ________ _________ _________ _________ _____.
________ ___ _________ _________ _______.
________ ____ ________ ____ _______ _________ _________ ______ _______ _____ _______.
_____ __________ ____ ____ _______ ____ ________ _____.
_____ _____ ________ ______ ________ _________ _______ ____ _____.
___ _____ _____ ______ ___ ________ _____.
_______ ________ _________ _______ ____ _______ ________ _______ _________ __________.
____ ____ ___ ______ _____ ___ ______ _______ _____ _________ ______.
________ _______ ______ ______ ______ __________ ______ ____ ____.
___ _______ ________ _________ _______ ______ __________ ________ _______.
_____ ________ ______ _______ _____ ________ ___ __________.
______ ____ ___ ___ _____ _________ _____ _________ ________ _______.
____ ____ _____ __________ _____ __________ _________ ___ __________ __________.
_____ _______ ___ ____ _____ ___ ___ ________ ___ _____ __________.
__________ _________ ____ _____ _____ _______ ______ _______ ____ __________.
________ ________ _________ ____ _________ ____.
_____ ___ ________ ____ _____.
_______ ______ ______ _________ _________.
_______ _____ ________ ____ ________.
_______ _______ _______ _______ ___ _____ __________ _________.
_______ ________ ____ ________ __________ ________ _______ _______ ___ _______ ______ ___.
______ ___ _______ ______ _________ _______ ___ ______ ___ ______ ____.
______ _________ __________ __________ ______ ________ ___ _______ ______ ____ ______ _________.
________ _________ ________ ___ __________ ________ _______ _________ __________.
____ ____ _______ ______ _________ _____ ______ ____ __________ _________ ______ _________.
__________ ______ __________ ______ ____ ______ ________.
______ _______ _________ _____ _______ ________ __________.
________ _____ __________ __________ _____ ___ ______ _________.
________ ______ _____ __________ _______ ____ _________ ______ ________.
___ ________ ____ ___ ________ ___ _____ _______ __________ _____.
__________ ______ ______ ____ __________ _________ ________.
_________ ____ _____ _________ ____ ________ _______ _______ ___ ______.
____ ___ ____ ____ _____ _______ __________ ______ _________.
___ ______ _______ ____ __________ ______ ___ _________ ________.
_______ _____ __________ ______ ____ ______ _____ ______ ______ _________ _____ ____.
_____ ____ __________ ____ _________ _______ ___.
_______ ____ __________ _________ __________ _________.
_________ ____ ________ ______ ______ ________ ______ _______.
_________ ___ ___ ________ ____ ______.
_______ __________ __________ ___ ______.
__________ ______ __________ ________ ___ ________ _________ __________.
___ ________ ________ ________ _______ ___.
__________ __________ _________ ___ ______ ____ _______.
________ _________ _______ __________ ______ ____ _________ _________ _____.
__________ ____ _______ ______ ________ ___ ______.
_________ _______ ____ _______ _______ ______ ____ _________ _________.
___ ___ _______ __________ ____.
________ ___ ___ _________ __________.
__________ __________ _____ ______ _______ _________.
_______ _____ _________ ___ _________.
________ ____ ___ __________ ______ _____ _____ ____ _______.
__________ ______ _______ ____ ________ ____ _______ _______ _______ _____ ____ _____.
_____ __________ __________ _______ __________ _________ ____ ________ _________ ______ _____.
____ ______ ________ ________ ______ _____.
________ ________ ________ ________ ______ ____ ________ __________.
_________ _______ ______ _______ _______ ________ ________ ____.
_________ _______ __________ ____ ____ ____.
__________ _____ __________ ____ _________ _________ ___ _____ ____ ___ _________.
___ _______ ____ __________ ______ _____.
______ ____ _____ __________ _________ ____.
_________ _______ __________ ____ _________ _________ __________ ________ __________ ______ ________.
______ ________ _______ ________ ______ ____ ________.
_________ ___ ____ ________ _______ _____ _______ ___ _____ __________ _______ ________.
____ _________ _______ ___ _____.
_________ __________ ____ ______ ________ ________ ______ _________ _______ ___ ___ _______.
________ _______ ________ ______ ___ ________ ______ __________ _________ _____.
____ ______ ______ _____ _________ ____ _______ ___ _________ _______ _________ ___.
____ ____ ________ ______ _______ ___ ____ _______ ________.
__________ _____ ______ ____ ___ _______ ___ _______.
________ _______ ____ ____ _____ _____ ______ _____ ______ ______ _______.
____ _________ _______ _______ _______ _____.
_______ _____ __________ ______ _______ __________ ___ _________.
________ __________ _______ _________ _________ _______ ________ ________.
________ _________ ___ _________ _______ ________ ________.
___ _________ _________ _______ ______ ______ _________ _____ _______.
______ _________ _______ ______ __________ ______ ___ ____ __________ ___.
_______ _______ ________ ______ ______ _________ ______ _________ ______ ___ ________ _________.
________ _________ ____ _______ ______ ___ ________.
___ ________ ________ ______ ____ ____ _______ ___ ___ _______.
___ ______ ________ ____ ____.
_____ _______ ________ ______ ______ _____ _______ _____ ________ ______ _____ _____.
______ ________ __________ __________ __________ _______ ___.
__________ ____ _________ ______ ______ ______ _________.
____ _____ _______ ________ ___ ________.
_____ _____ ______ _____ __________ __________.
_________ ______ _______ __________ __________.
____ _________ ____ ______ ____ ____ ____.
________ ______ ___ _________ ______ ____.
_________ ____ _________ ______ _______ ____ ___ _______ ______ _____ _____.
_____ ___ ______ ___ _____ __________ _____ _____ ____ _____.
_________ ____ _____ ______ _________ __________ _________.
_________ ____ ___ ___ _______ _____ __________ _________ _________.
______ ______ _____ _______ __________ _____ _____ ________ ______ _________ ______.
___ _________ _______ ___ __________ __________ _____ ___ _______ _________.
_____ __________ ____ _________ _____ __________ _____.
_______ _____ ___ ___ ______ ______ _______ ____ ________.
______ ________ ______ ________ ________ ___ _________ __________ _________ _________ ________.
__________ _____ ___ _______ ______ ____.
____ ___ _____ _____ _______ _______ ______ ____.
___ __________ _______ ______ _______ _____ _______ _______ ____ _____ __________.
_________ _______ ______ ______ _____ _______.
________ ___ ______ ____ ___ _________ ____ _____ ____ ____ ____.
______ __________ __________ ________ ___ ____ ______ _____ ______ _________.
_______ ______ _____ ______ _____ ___.
_______ _________ ____ __________ ____ ________.
_______ ___ ________ ______ _________ ________ ___.
____ _______ ______ _____ _______ ____ ________ _______ _____ ________.
___ ______ _________ ______ ________ _______.
___ _____ ____ _________ ______ __________ ___ ________ ________ _____ _________.
___ _____ ________ _________ _________ _______ ____.
_____ __________ _______ _________ _______ ________ _____ _______ __________.
________ ________ __________ ____ ___ ________ ___ ____.
________ _______ ____ _______ ____ _______ ________ _________.
__________ ______ __________ ______ ______ ________ ___ ________.
______ _______ _______ ____ ________ ____ _________ _________ _______ _______.
__________ _____ ________ ______ _______ ______ ____ _______.
_________ _________ ___ ______ _____.
______ ________ _________ ___ ________ ____.
_______ _________ _____ __________ _______ ________ _______ __________ _________ ________ ___.
_______ _________ ___ ___ ______ ____ ______ ____ _______ ____.
____ ____ __________ _________ ________ __________.
___ ___ _______ _____ ____ _____ _______ ___ ________ __________.
_____ _____ _________ ______.
Get Full Answer on WhatsApp