Woah, okay, things just get out of my hands. Sorry about the confusion I created. I was far from expecting such a precise answer with my little messy-funny math-thingy.

First and foremost, I'm totally fine: I'm not trying hard to achieve anything and I need nothing for my script code. I was just having fun trying to come up with a mathematical proof that this algorithm works (actually creates a connected graph).

For example, In 3, you say "alternatively last" after an infinite number of steps, which is a bit problematic.

Yeah, sure. Forget "infinite", just "any number of step", cause, sure, you need a "last" step of course.

First one just says this: "You can't make a connected graph not connected by adding new vertexes."

That's a very concise definition, indeed. GG to you.

This is trivially true already.

That, however, is personal. While I totally agree with it, I don't feel getting away with "bah, it's trivial" is a good attitude. Well, being AIW players, we can't be put off by the perspective of challenge, can we?

But, yeah. Your oneliner is good. I would just be a little more nitpicking (I think it's only fair

) and add "... by adding

*one* new vertex linked to at least one other (previously created so part of the connected graph) vertex". Then, by adding multiple vertices, one at a time, each respecting this condition, the graph will still be connected after

~~an infinite~~ any number of

~~steps~~ added vertices. (Because, clearly, I can add multiple vertices to a connected graph that would produce a non-connected graph: by putting them aside, linked with no vertices.)

if I were to code these things, I would just produce a fully connected graph with every possible vertex included, and erase the vertices one by one.

Did you meant "with every possible

*edges* included, and erase

*edges* one by one"? Because there is no "every possible vertices" (at least it doesn't seem to be a finite number).

Even so, would you check if the graph is still connected after each edge removal, and step back if it's not any more? That sounds like a lot of computational overhead. And how would you stop? When reaching a target number of edges?

I don't understand that last sentence. Would you explain it further, please?