Prove that for any graph G, the connectivity is less that the minimum degree

[sunnyceej]

prove that for any graph G, kappa (G) ≤delta (G).

 

[mathwonk]

define your terms.

 

[James4]

suppose the connectivity is larger than min deg and look at the vertex v with min deg.
How many elements (nodes / edges) need to be removed to disconnect v from the rest of G?

 

[Bacle2]

prove that for any graph G, kappa (G) ≤delta (G).

What about the graph {(x,y)} on two vertices {x,y}, i.e., a tree with one edge?

EDIT: OP, you may want to square up your title with your question. Do you want less-than, or less-than-or-equal-to?

 

[blue_raver22]

I would like to clarify that the minimum degree of a graph G refers to the smallest number of edges incident to a vertex in G. Similarly, the connectivity of a graph G, denoted as κ(G), refers to the minimum number of vertices that need to be removed in order to disconnect G.

To prove that for any graph G, the connectivity is less than the minimum degree, we can use a proof by contradiction. Suppose there exists a graph G where the connectivity, κ(G), is greater than or equal to the minimum degree, δ(G). This would mean that there exists a set of vertices in G, let's say S, with a size of at least δ(G), such that removing these vertices would disconnect G into two or more components.

However, since the minimum degree in G is δ(G), each vertex in S must have at least δ(G) edges incident to it. This means that the removal of S would result in the removal of at least δ(G) * δ(G) = δ(G)^2 edges from G. But this contradicts the fact that G is still disconnected after the removal of S, as there must be at least δ(G)^2 + 1 remaining edges in G in order for it to remain connected. Therefore, our initial assumption that κ(G) ≥ δ(G) is false, and we can conclude that for any graph G, the connectivity is less than the minimum degree.

Now, to prove that for any graph G, κ(G) ≤ δ(G), we can use a similar proof by contradiction. Suppose there exists a graph G where the connectivity, κ(G), is greater than the minimum degree, δ(G). This would mean that there exists a set of vertices in G, let's say S, with a size of at least κ(G), such that removing these vertices would disconnect G into two or more components.

However, since the minimum degree in G is δ(G), each vertex in S must have at least δ(G) edges incident to it. This means that the removal of S would result in the removal of at least κ(G) * δ(G) = κ(G) * δ(G) edges from G. But this contradicts the fact that G is still disconnected after the removal of S, as there must be at least κ(G) * δ(G) + 1 remaining edges in G in order for it to remain connected. Therefore, our initial assumption that