Theorem Gallai subdegree Meged Meged, T., (1987), "On the complexity of finding a large clique", in Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, pp. 304-315. "It is a well-known fact that every graph with n vertices and m edges has at least one vertex of degree at least (m/n)." Let G be a graph with n vertices and m edges. Let d(v) denote the degree of vertex v in G. Then there exists a vertex v such that d(v) >= (m/n). Proof: Suppose for contradiction that every vertex has degree less than (m/n). Then the sum of degrees is less than n * (m/n) = m, which contradicts the Handshaking Lemma. Therefore, there must exist a vertex with degree at least (m/n). Q.E.D.