Graph Theory In Details Prove that for K fixed almost every

Graph Theory

In Details

Prove that for K fixed, almost every graph is k - connected.

Solution

Let H_n,k denote the class of all connected graphs of order n with k pendant vertices. We may assume that 1kn1 and hence n3. We first consider the question of maximizing the algebraic connectivity over H_n,k We now define a collection of graphs, denoted P^k_n, which have exactly k pendant vertices and hence are members of H_n,k. For k not equal to n 2, the graph P^k_n, is obtained by adding k pendant vertices adjacent to a single vertex of the complete graph K_nk. There is no graph of order n= 3 with exactly one pendant vertex. For n4 and k=n2, the graph Pⁿ²_n is obtained by adding n 3 pendant vertices adjacent to a pendant vertex of the path P_3.