Let $v_1,v_2,...,v_k$ be k distinct vertices of a k-connected graph G. Let H be the graph formed by adding a new vertex w of degree k that is adjacent to to each of the $v_1, v_2,..., v_k$. Show that $kappa(H)=k$

Question

Let $v_1,v_2,...,v_k$ be k distinct vertices of a k-connected graph G.  Let H be the graph formed by adding a new vertex w of degree k that is adjacent to to each of the $v_1, v_2,..., v_k$.  Show that $kappa(H)=k$

fibonaccichick666 · Answer

So, isn't it when we add vertex w, the degree sequence is {k+1,k+1,...,k+1,k}  therefore the smallest vertex cut comes when we remove w which removes k edges?

fibonaccichick666 · Answer

@dan815 can you check the above?

fibonaccichick666 · Answer

nope that's not right h/o

fibonaccichick666 · Answer

ok so we remove the vertices of G which there are k of leaving w disjoint.  Yea?

dan815 · Answer

okay just one question what does it mean addding w of degree k, adj to every vertex

fibonaccichick666 · Answer

so we toss in a vertex w, this vertex is the connected by an edge to every vertex of G

dan815 · Answer

right so there are a total of k new edges right?

fibonaccichick666 · Answer

yea

dan815 · Answer

okay now so what does this kappa(h)=k want

fibonaccichick666 · Answer

the cardinality of the minimum vertex cut

dan815 · Answer

oh okay! yes that is true it has to be k!

dan815 · Answer

just k*

dan815 · Answer

the minimum cut must happen right beside a point

dan815 · Answer

|dw:1429102956463:dw|