MathDB

Consider a graph with

n

vertices and

\frac{7n}{4}

edges. (a) Prove that there are two cycles of equal length. (25 points) (b) Can you give a smaller function than

\frac{7n}{4}

that still fits in part (a)? Prove your claim. We say function

a(n)

is smaller than

b(n)

if there exists an

N

such that for each

n>N

a(n)<b(n)

(At most 5 points) Proposed by Afrooz Jabal'ameli

Problem Statement