show that the degree of every vertex ix a nonseprable graph is at least two
Answers
How can you show that a graph with n vertices and with vertex connectivity k must have at least n/2 edges? How can you further show that the degree of every vertex in a non-separable graph is at least two?
This will probably leave out a few edge How can you show that a graph with n vertices and with vertex connectivity k must have at least n/2 edges? How can you further show that the degree of every vertex in a non-separable graph is at least two?
First I want to clarify a few definitions. We say that a connected graph is k -connected if the removal of fewer than k vertices (and all the incident edges on said k vertices) results in a graph that is still connected. Notice that this implies that the graph is 1,...,k -connected for every integer up to k . A graph G is said to have connectivity k if k is the largest integer for which G is k -connected. So, when a graph is said to be k -connected, it is not necessarily the case that the graph has connectivity k , but it is the case that the graph has connectivity at least k . I should mention that these definitions are actually the common definitions for k -vertex connected and vertex-connectivity, since there is an appropriate analog when it comes to edge connectedness.
The general statements are actually these two:
If G is a k -connected graph then every vertex in G has degree at least k .
If G is a k -connected graph then it has at least kn2 edges.
The second statement simply follows from the first by applying the handshaking lemma (hopefully the reader can tie the knots here). As for that last part about non-seperable graphs, it is simply a special case of the first statement. Indeed, a graph is said to be non-seperable if it is 2 -connected, and therefore in any non-separable graph, every vertex has degree at least 2 (according to the first statement).
Now ask yourself, can a k -connected graph have a vertex with degree less than k ? What if it had a vertex with degree j<k . Consider removing the j neighbours of said vertex. Is this graph still connected ? Is this vertex reachable from every other vertex, let alone any other vertex?
That’s roughly the idea. There is a result more general than the first which not only assures that a k -connected graph has every vertex with degree at least k but that there k internally disjoint paths between any pair of non-adjacent vertices. This is a classic result called Menger’s Theorem. of fewer than k vertices (and all the incident edges on said k vertices) results in a graph that is still connected. Notice that this implies that the graph is 1,...,k -connected for every integer up to k . A graph G is said to have connectivity k if k is the largest integer for which G is k -connected. So, when a graph is said to be k -connected, it is not necessarily the case that the graph has connectivity k , but it is the case that the graph has connectivity at least k . I should mention that these definitions are actually the common definitions for k -vertex connected and vertex-connectivity, since there is an appropriate analog when it comes to edge connectedness.
The general statements are actually these two:
If G is a k -connected graph then every vertex in G has degree at least k .
If G is a k -connected graph then it has at least kn2 edges.
The second statement simply follows from the first by applying the handshaking lemma (hopefully the reader can tie the knots here). As for that last part about non-seperable graphs, it is simply a special case of the first statement. Indeed, a graph is said to be non-seperable if it is 2 -connected, and therefore in any non-separable graph, every vertex has degree at least 2 (according to the first statement).
Now ask yourself, can a k -connected graph have a vertex with degree less than k ? What if it had a vertex with degree j<k . Consider removing the j neighbours of said vertex. Is this graph still connected ? Is this vertex reachable from every other vertex, let alone any other vertex?
That’s roughly the idea. There is a result more general than the first which not only assures that a k -connected graph has every vertex with degree at least k but that there k internally disjoint paths between any pair of non-adjacent vertices. This is a classic result called Menger’s Theorem.