MathLabs

Problem 4

A set of positive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let P(n)=n2+n+1P(n)=n^2+n+1. What is the smallest possible value of a positive integer bb such that there exists a non-negative integer aa for which the set {P(a+1),P(a+2),…,P(a+b)}\{P(a+1),P(a+2),\dots,P(a+b)\} is fragrant?
Step 3 of 5: Too few edges to cover every vertex
Previous stepNext step
In plain words

Three edges can touch at most six vertex-slots, and covering all five vertices of the pentagon-shaped gap-graph turns out to be impossible with edges restricted to gaps 2,3,42,3,4 only.

at most 3 edges among 5 vertices ⇒ some vertex has degree 0\text{at most }3\text{ edges among }5\text{ vertices}\ \Rightarrow\ \text{some vertex has degree }0
Detailed analysis

With at most 33 edges total (one each of gap 22, 33, 44) among the 55 vertices a+1,…,a+5a+1,\dots,a+5, and no edges of gap 11 allowed, a direct check of which vertex-pairs these gaps can connect shows it is impossible for all 55 vertices to have degree ≥1\ge1 simultaneously: some vertex is always left isolated. This contradicts the fragrant condition (every element needs a partner), so b≤5b\le5 is impossible.