Freaks City

Definition of Degree The degree of a vertex (v) in a graph (G), denoted by (d_G(v)), is the number of edges of (G) incident with (v), with each loop counting as two edges. (J.A. Bondy, Graph Theory) Two fundamental results follow from this definition: Handshaking Theorem: For any graph (G), [ \sum_{v \in V} d(v) = 2m ] where (m) is the number ...

Consider two sequences of non-negative integers \(p_1 \ge p_2 \ge \dots \ge p_n\) and \(q_1 \ge q_2 \ge \dots \ge q_m\) satisfying \(\sum_{i=1}^n p_i = \sum_{i=1}^m q_i\). The Gale-Ryser theorem states that a simple bipartite graph exists with left vertices having degrees \(p_1, p_2, \dots, p_n\) and right vertices having degrees \(q_1, q_2, \d ...