Graph theory:

>>9066893
The connectivity is a measure of how many EDGES at minimum must be removed to render the graph disconnected.

The minimum degree of n-2 tells you that every connected component has connectivity n-2

All you have to do is prove that it is 1 component to begin with.

>>9066893
>been studying graph theory for a few weeks
>unable to prove that
>mfw brainlet
I should give up

>>9066909
I should have specified, the book uses the definition of "vertex connectivity" as in the minimum size of a vertex cut set.
But yeah I've seen there are two nonequivalent definitions floating around. That's weird.

>>9066909
The minimum degree of n-2 tells you that every connected component has connectivity *at least* n-2

>>9066893
Maybe induction

>>9066913
Isn't it "at most"?
Even though the book doesn't mention edge connectivity at all, I'm guessing it can't be more than minimum degree since you can always get away with deleting all the edges that connect the vertex with the smallest degree and you'd end up with one more component (isolated vertex).
At least that's how it works with vertex connectivity (well unless the minimum degree is n-1 in which case the graph is complete and you'll never end up with more than one component)

>>9066918
honestly seems overly complicated for the type of question it seems to be supposed to be.

>>9066925
Forget those, my bad.
Now I'm interested in the answer.

I'm trying to think about how to remove edges from K_n (v-connect = n-1).

It would have to be no more than one edge per vertex.

At least 1 edge must be removed from K_n to get MinDeg = n-2...

Combinatorial aside: # of non-identity involutions

>>9066935
Got it.

You start with two vertices of deg n-2 that are not adjacent to each other.

Each one of those verticies is adjacent to every other vertex (n-2 of them)

Use Menger's Theorem

>>9066935
the only thing I know about that is that you have to have an even number of vertices with degree=(n-2), but beyond that...
I'm just starting out but I feel like a brainlet already, graph theory seems comfy but it's a mindfuck. I was much more at ease with more "verbal" mathematics.
Plus some of the questions in the book are giving me a real hard time, sometimes up to 20-30 mins, and I feel like a brainlet because I don't get whether they're supposed to be trivial or not.

>>9066951
Don't know Menger's theorem yet. As I said I'm just starting out. So it seems wasn't too far off with what I said in the OP? Still can't write it formally tho, it's frustrating as FUARK

>>9066955
What book are you using btw?

>>9066958
Don't use menger then.

You can remove n-3 of any of the n-2 and it will still be connected right?

>>9066965
and removing all n-2 will disconnect it
so the vertex connectivity is exactly n-2

>>9066959
Combinatorics and Graph Theory, Second Edition
>>9066965
Yeah but it's not that simple since it's not as if I can only ever remove vertices from ONE vertex's neighborhood. For instance, I can delete that one vertex after a number of steps, and then I'd have to do start over again until I delete the vertex whose neighborhood I'm deleting and so on. So I think it would require a longer proof to be written formally but yeah, I see what you mean.

>>9066992
I think if you remove one of the min degree vertices, you can reduce the problem size and work it out with mathematical induction as well.

Anyway, it's been fun.

https://www.youtube.com/watch?v=tYzMYcUty6s

>>9066893
the idea is correct, just need to write it formally since maths is literally autism

>>9066893
not sure what "connectivity (n-2)" means, but i suppose it means that you need to remove n-2 edges for it to become disconnected.

if that's the case - suppose you pulled out n-3 edges. look at one of the components, it has a vertex v. v has degree at least n-2 so it still has a neighboring vertex u.
now, consider the joint neighborhood of u and v in the original graph. both of them had at least n-3 edges going out to that neighborhood, and there are only n-2 other options, so either they all hit the same n-3 vertices or they cover all the n-2 vertices (both hitting n-4 of them)

notice that removing n-3 vertices, we still have at least n-4 vertices in the neighborhood

now, this is a bit of an overkill, since even if we show that we always have more that n/2 then it would mean that we get the majority of vertices in this component.
but obviously this argument is completely symmetric to any component, so each component gets the majority, and thus they are one and the same.

>>9067169
I meant vertex connectivity, my bad. Still, it's weird that everyone assumes it's edge connectivity. Is that the most common definition? Maybe I should find another book.
Regardless, I'm having trouble with your explanation. You're saying that since u and v have at most one different element in their respective neighborhoods (excluding each other), then the graph has to be connected (I'm assuming this is obtained by applying the reasoning to all such pairs)?
I haven't given much thought to edge connectivity. To be frank Graph Theory is much harder than I expected, and certainly much harder than any topic I've had the occasion of studying (I'm an undergrad).
Hopefully one day this'll all be trivial to me.