edited by
6,343 views
33 votes
33 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.
edited by

5 Answers

Best answer
40 votes
40 votes

  1.    (i) Not a cut. We have spanning tree after removing this edges.
       (ii) This is cut. We break the 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$ 
    We know that 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
5 votes
5 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.
edited by
4 votes
4 votes
Answer :-

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
0 votes
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

Related questions

39 votes
39 votes
5 answers
1
Kathleen asked Sep 23, 2014
8,748 views
The number of articulation points of the following graph is$0$$1$$2$$3$
13 votes
13 votes
3 answers
2
Kathleen asked Sep 23, 2014
2,354 views
Show that the formula $\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right]$ is not a tautology.Let $A$ be a tautology and $B$ any other formula. Prove that $(A \ve...
34 votes
34 votes
2 answers
3
Kathleen asked Sep 23, 2014
5,024 views
Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.