/sci/ - Science & Math

I'm having a problem with a question in a graph theory entry level book, I already made a thread but I figure it'll be twice as fast posting it here. Anyway, in case there are some experts (though I doubt you need to be one), here goes.

How do I go about proving that a graph with order n and minimum degree (n-2) has VERTEX connectivity (n-2) as well?

I mean I know, intuitively that if I delete a certain number of vertices and end up with 2 or more components, then each component must contain a vertex u that had degree n-2 in the initial graph, and one other component must contain the one vertex v that wasn't it his neighbourhood. And since these two vertices have the same neighborhood with n-2 vertices, you'd have to delete all of them for there not to exist a path between u and v.
However this seems far fetched and I don't really know how to write the first part formally.
Is there a simpler proof I'm missing? The exercise is literally at the beginning of the book and all the proofs seem much easier.

But since there are like 5 people on /sci/ currently, I'm guessing I'm gonna get the same people anyways.

How do I go about proving that a graph with order n and minimum degree (n-2) has connectivity (n-2) as well?

I mean I know, intuitively that if I delete a certain number of vertices and end up with 2 or more components, then each component must contain a vertex u that had degree n-2 in the initial graph, and one other component must contain the one vertex v that wasn't it his neighbourhood. And since these two vertices have the same neighborhood with n-2 vertices, you'd have to delete all of them for there not to exist a path between u and v.
However this seems far fetched and I don't really know how to write the first part formally.
Is there a simpler proof I'm missing? The exercise is literally at the beginning of the book and all the proofs seem much easier.

Hello! i have a few graph theory questions...

Can someone please explain the proof to prim's algorithm (or a proof that it does indeed give you the minimum spanning tree)?

Can someone explain to me how the upper bound algorithm really gives you the upper bound of possible total weights of a tour?

Is it possible for a graph given to you by the lower bound algorithm be a hamiltonian cycle?

And finally, how would one go about comparing the speed of different tsp solving algorithms, like you guys got any resources on how to find the big O notation for brute force, a basic branch and bound algorithm, ant colony, nearest neighboor, and even some iterative improvement algorithms.

Please help, I'm stuck on these things, and needed to be read for going back to school.

hi
having problems with some number theory:
find all positive integers x,y,z that <span class="math">x^2+1[/spoiler] and <span class="math">y^2+1[/spoiler] are prime and
<span class="math">(x^2+1)(y^2+1)=z^2+1[/spoiler]

pic not related