Introduction to Graph Theory · Problem 2.6

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · erdos-gallai-degree-inequality

Problem

Let G=(V,E)G = (V, E) be a simple graph. Let SS be a subset of VV, and let k=∣S∣k = |S|. Prove that ∑v∈Sdeg⁡v≤k(k−1)+∑v∈V∖Smin⁡{deg⁡v,k}.\sum_{v \in S} \deg v \leq k(k-1) + \sum_{v \in V \setminus S} \min\{\deg v, k\}.

Browse the problem library