MathDB

Lesser degree on the edges

Source: 239 2013 J4

August 7, 2020

combinatoricsgraph theory

Problem Statement

We are given a graph

G

with

n

edges. For each edge, we write down the lesser degree of two vertices at the end of that edge. Prove that the sum of the resulting

n

numbers is at most

100n\sqrt{n}