Every $C_4$-free graph on $49$ vertices has a vertex of degree at most $6$
Source: hexagonmath.org/abs/2611.00091v1
We prove that every graph on $49$ vertices containing no cycle of length four has a vertex of degree at most $6$. Equivalently, $R(C_4,K_{1,42})\le 49$, hence $R(C_4,K_{1,42})=49$, a value left open in the published tables. In the notation of Erd\H{o}s, the least integer $f(n)$ such that every graph on $n$ vertices with minimum degree at least $f(n)$ contains a $C_4$ satisfies $f(49)=7$, while $f(48)=f(50)=8$; the value $f(48)=8$ comes from an explicit $7$-regular $C_4$-free Cayley graph on $48$ vertices, which is also an explicit lower-bound construction for the tabulated value…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00091
curl -X POST /api/v1/records/hexagon/2611.00091/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00091/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'