Thread: interesting problem about two-connected

Dear all,
I encountered a new problem recently about two-connected graphs, of course there was no solution mentioned there. I've been thinking about it some days and could n't solve it. Any body has an idea? Here is the question:

Let G be a two-connected graph. Prove that its vertices can be numbered as v1, v2, . . ., vn in such a way that for all i = 1, 2, . . ., n, both sets {v1, v2, . . ., vi} and
{vi , vi+1, . . ., vn} induce connected graphs.

I'd probably assume one is the other and use an adjacency matrix as a start. But I suspect this is homework, in which case you should tell us what you've tried already and serve as a jumping off point for others to give you hints.

Also moving this to math...

Actually, none of my tries succeeded. But intuitionally what I expect is lets suppose that there is not such a thing then assume the one with minimum components on each side summed over all i's . then we should reorder some vertices so that this number reduces

Originally Posted by Lynx_Fox

I'd probably assume one is the other and use an adjacency matrix as a start. But I suspect this is homework, in which case you should tell us what you've tried already and serve as a jumping off point for others to give you hints.

Also moving this to math...