1.1k views

Let $G$ be a connected, undirected graph. A cut in $G$ is a set of edges whose removal results in $G$ being broken into two or more components, which are not connected with each other. The size of a cut is called its cardinality. A min-cut of $G$ is a cut in $G$ of minimum cardinality. Consider the following graph:

1. Which of the following sets of edges is a cut?

1. $\left\{(A, B), (E, F), (B, D), (A, E), (A, D)\right\}$
2. $\left\{(B, D), (C, F), (A, B)\right\}$
2. What is cardinality of min-cut in this graph?
3. Prove that if a connected undirected graph $G$ with $n$ vertices has a min-cut of cardinality $k$, then $G$ has at least $\left(\frac{n\times k}{2}\right)$ edges.
edited | 1.1k views

1. Not a cut. We have spanning tree after removing this edges.
This is cut.we break graph into two pieces.

2. Min cut size is $2. \{BC,CF\}$. Removal these two edges disconnects $C$ from the remaining graph.

3. Always cardinality of min-cut will be $\leq$ min-degree of the graph
So, $k \leq$ min-degree of the graph
min-degree of the graph $\geq k$
WKT sum of degrees of all vertices $= 2 *$ number of edges.
minimum degree $\times n \leq 2\times |E|$, where $n$ is number of vertices, $|E|$ is number of edges.
$=k*n \leq 2|E|$
$\Rightarrow |E| \geq (n*k / 2)$
edited by
+10

Always cardinality of min cut will be <= min degree of the graph

So k <= min degree of the graph

==> min degree of the graph >= k

WKT sum of degrees of all vertices = 2 * number of edges

==> min degree * n <= 2*e where n is number of vertices, e is number of edges

==> k*n <= 2e

==> e >= (n*k / 2)

+1

This might help ...

1 this will not disconnect the graph. Make and check.

2- it will disconnect the graph. and remember the disconnected graph can have more than one vertices

we can always make a graph disconnected by removing the edges equal to min degree of a node. not believe me . remove the two edges BC and CF . as we can get a islolated vertex. tit will become disconnected .

on the same basis the proof can be done,

if k edges has to be removed , to make a graph disconnected . that means . edge connectivity should be ;less than equal to  min degree edges.

edge connectivity = k (min degree) < = 2e/v

so the number of edges in such graph will be atleast  (n*k)/2.
edited by

a

(i) Not a cut. We have spanning tree after removing this edges.

(ii) This is cut.we break graph into two pieces.

B) Min cut size -> 2. (BC,CF). Removing this two edges disconnects C from remaining graph.

C)  sum of degree of all vertices = 2E (by handshaking lemma)
d1+d2+d3+.................+dn = 2E
replace each degree with min degree
Also since we know min-cut<=min-degree therefore here we can say
k +k+k+................+n times <=2E
nk<=2E
hence,

E>=nk/2
(a) (1) by removing {(a,b)(e,f)(b,d)(a.e)(a,d)} graph is not disconnected , it will give 0 components

(2) by removing {(b,d)(c,f)(a,b)} graph will be disconnected into two components k1{bc} ,k2{aefd}

(b) if we want to disconnect then we should take any vertice which hav min degree and disconnect the edge , whch are connected to that min degree virtice , it will give one isolated vertice

therefore we can say that min-cut of graph = min degree of graph=2

(c) as i have done above question (b) lets min-cut have cardinality k , assume that min degree vertice have degree =k

in question it has been asked that atleast no . of edges so, lets assume that all the virtices have k(min degree) so , by hand shake theoram 2*edges = n *k => edges = (nk)/2
(a) (i) Not a cut. (ii) It is a cut.

(b) 3. {(B,D),(C,F),(A,B)} and {(A,E),(D,E),(E,F)} and {(B,D),(B,C),(A,B)}. Cardinality of each cut set is 3.
+1
(a)-> ii is wrong as well as (b) is wrong.
+1
(a)-> (ii) is correct but (b) is wrong.

1
2