Collection of Maths Problems

Graph operations

Task number: 3959

• Variant

  Prove that for a graph \(G\) and an edge \(e \in E(G)\) holds that \(k_e(G) - 1 \leq k_e(G - e) \leq k_e(G)\).

• Solution

  The lower bound:

  If \(S\) is the smallest edge cut of \(G-e\), then \(S\cup e\) is (not necessarily smallest) edge cut of \(G\), hence \(k_e(G)\leq k_e(G - e)+1\).

  The upper bound:

  For any edge cut \(S\) of \(G\), the set \(S\setminus e\) is the edge cut of \(G-e\). Note that when \(e\notin S\) then \(|S|=|S\setminus e|\).

• Variant

  Prove that for a graph \(G\) and a vertex \(v \in V(G)\) holds that \(k_v(G) - 1 \leq k_v(G - v)\).

• Solution

  If \(S\) is the smallest vertex cut of \(G-v\), then \(S\cup v\) is (not necessarily smallest) vertex cut of \(G\), hence \(k_v(G)\leq k_v(G - e)+1\).

• Variant

  Find a graph for which for which \(k_v(G - v) \not\leq k_v(G)\).

• Solution

  Take for \(G\) a cycle \(C_3\) with an extra leaf \(v\). Then \(k_v(G)=1\) as the neighbor of \(v\) is a vertex cut, while \(k_v(G-v)=k_v(C_3)=2\).

• Variant

  Prove that the edge removal does not reduce the vertex connectivity of a graph by more than 1.

  In other words, \( k_v (G-e) \ge k_v (G) -1 \).

• Solution

  Denote \(e=(u,v)\) and consider the smallest vertex cut \(S\) of \(G-e\). If \(S\) contains \(u\) or \(v\), then it is also a cut of \(G\).

  If \(G\setminus S\) has a component disjoint with \(\{u,v\}\), then \(S\) is still a cut of \(G\).

  So we are left with the case that \(G\setminus S\) has two components, one containing \(u\) and the other \(v\). If the component containing \(u\) has another vertex, then \(S\cup u\) is a cutset of \(G\). Analogously for \(v\).

  Now we have the case that the smallest cut \(S\) separates only the two vertices \(u\) and \(v\). If \(G\setminus e\) contains another pair of non-adjacent vertices \(x\) and \(y\) (one of them may be \(u\) or \(v\)), then \(S’=V_G\setminus\{x,y\}\) is also vertex cut of \(G-e\) of the mininum size, the same as the size as \(S\). Such cut \(S’\) would be also a cut for \(G\).

  Finally, the only remaining case is when \(G\) is complete graph \(K_n\). Then its vertex connectivity is \(k_v(K_n)=n-1\). For any \(e\in E(K_n):k_v(K_n-e)=n-2\).

• Variant

  Prove that the edge contraction does not reduce the vertex connectivity of a graph by more than 1.

  In other words, \( k_v (G / e) \ge k_v (G) -1 \).

• Solution

  Denote \(e=(u,v)\) and by \(w\) the vertex resulting by the contraction of \(e\). Consider the smallest vertex cut \(S\) of \(G/e\). If \(S\) does not contain \(w\), then it is also a cut of \(G\).

  Otherwise \(S\cup \{u,v\}\setminus \{w\}\) is a cut of \(G\) of size \(|S|+1\).