MathDB

N2

Part of 2020 IMO Shortlist

Problems(1)

A prime graph

Source: ISL N2

7/20/2021
For each prime pp, construct a graph GpG_p on {1,2,…p}\{1,2,\ldots p\}, where m≠nm\neq n are adjacent if and only if pp divides (m2+1−n)(n2+1−m)(m^{2} + 1-n)(n^{2} + 1-m). Prove that GpG_p is disconnected for infinitely many pp
prime numberscombinatoricsgraph theoryConnected graphsIMO ShortlistIMO Shortlist 2020