Subgraphs intersecting any Hamiltonian cycle (Q1077429): Difference between revisions

Let G be a subgraph of K(n), the complete graph on n vertices, such that (i) its edges cannot be represented by fewer than k vertices, (ii) every hamiltonian cycle of K(n) contains at least one edge of G and no proper subgraph of G has this property. P. Erdős posed the question of determining min e(G). In particular, is there an absolute constant c such that e(G)\(\geq c\cdot k\cdot n?\) The minimum is calculated for all \(n\geq 3\) and \(k\leq n/2\), and the second part of the question is answered in the affirmative with \(c=1/4\) being the best possible constant.