The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 votes

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.
asked in Graph Theory by Veteran (59.5k points)
edited by | 814 views

5 Answers

+17 votes
Best answer
  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)$

answered by Boss (42.6k points)
edited by

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)


This might help ...

+4 votes
The answer for a

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

answer for B,

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.
answered by Boss (15.7k points)
edited by
+4 votes
Answer :-


(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

answered by (431 points)
0 votes
(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
answered by Active (4.8k points)
–4 votes
(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.
answered by Boss (34k points)
(a)-> ii is wrong as well as (b) is wrong.
(a)-> (ii) is correct but (b) is wrong.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,939 questions
45,453 answers
48,209 users