4.1 [GATE 1989 2 Marks] Which of the following graphs is/are planar? (see Figure) G1, G2, G3
(a) G1 only
(b) G1 and G2
(c) G2 only
(d) G2 and G3
Solution: Answer: (c) G2 only
G1 is K3,3 – Complete bipartite graph with 3+3 vertices. By Kuratowski’s theorem K3,3 is non-planar.
G2 is Cube graph – 8 vertices, 12 edges. It can be drawn on plane without edge crossing. So it is planar.
G3 is graph with 6 vertices where 3 diagonals intersect at a point. If we consider intersection as crossing, it contains K3,3 as subgraph, so non-planar.Planar sirf G2 hai.Concept: K5 and K3,3 are the two minimal non-planar graphs. Cube is always planar.
4.2[GATE 1990 : 2 Marks] A graph is planar if and only if,
(a) If does not contain subgraphs homeomorphic to K5 and K3,3.
(b) It does not contain subgraphs isomorphic to K5 or K3,3.
(c) It does not contain subgraphs isomorphic to K5 and K3,3.
(d) It does not contain subgraph homeomorphic to K5 or K3,3.
Solution: Answer: (d)
This is direct Kuratowski’s Theorem.
Theorem states: A graph is planar iff it does not contain a subgraph that is a subdivision (homeomorphic) of K5 or K3,3.Isomorphic ka matlab exact same, but homeomorphic ka matlab edges ke beech me vertices insert karke banaya hua graph. So correct word is homeomorphic and condition satisfies (d).
4.3[GATE 1991 : 2 Marks] The maximum number of possible edges in an undirected graph with ‘a’ vertices and ‘k’ components is _.
Solution:
Maximum edges ke liye, hame graph ko as unbalanced as possible banana hoga.k components hai, toh k−1 components me sirf 1-1 vertex rakh do (0 edges), aur saare bache hue vertices ek hi component me daal do.Bache hue vertices = a−(k−1)=a−k+1Ab us bade component ko complete graph bana do. Complete graph me edges = n(n−1)/2So, n=a−k+1Max edges = 2(a−k+1)(a−k)Answer: (a−k)(a−k+1)/2
4.4[GATE 1992 : 1 Mark] A non-planar graph with minimum number of vertices has
(a) 9 edges, 6 vertices
(b) 6 edges, 4 vertices
(c) 10 edges, 5 vertices
(d) 9 edges, 5 vertices
Solution: Answer: (c) 10 edges, 5 vertices
Smallest non-planar graphs are K5 and K3,3.K3,3 has 6 vertices, 9 edges.
K5 has 5 vertices, 10 edges. Minimum vertices ki baat ho rahi hai, to K5 will be the answer because 5 < 6.K5 me edges = 5∗4/2=10.
Ye lo bhai, agle 6 questions ka solution:
4.6[GATE 1994 : 1 Mark] The number of distinct simple graphs with upto three nodes is
(a) 15 (b) 10 (c) 7 (d) 9
Solution: Answer: (c) 7
Distinct ka matlab yaha unlabelled / non-isomorphic graph hai.1 node pe: 1 graph (single vertex)2 nodes pe: 2 graphs (0 edge, 1 edge)3 nodes pe: 4 graphs (0 edge, 1 edge, 2 edges-path, 3 edges-triangle)Total upto 3 nodes = 1 + 2 + 4 = 7 Agar labelled count karna hota to formula 2n(n−1)/2 hota, total 1+2+8=11 hota, par options me 7 hai to GATE ne unlabelled maana hai.
4.7[GATE 1995 : 2 Marks] Prove that in a finite graph, the number of vertices of odd degree is always even.
Solution:
Ye Handshaking Lemma se direct proof hai.Handshaking Lemma: ∑v∈Vdeg(v)=2∣E∣Matlab sum of degrees hamesha even hota hai kyunki 2∣E∣ even hai.Ab vertices ko 2 set me baant do:Veven = even degree wale verticesVodd = odd degree wale verticesTo: ∑Vevendeg(v)+∑Vodddeg(v)=2∣E∣Pehla term ∑Veven to even hai hi (even ka sum even).
2∣E∣ bhi even hai.To even = even + ∑VoddIska matlab ∑Vodd bhi even hona chahiye.Odd numbers ka sum even tabhi hota hai jab odd count even ho.Hence, number of vertices of odd degree is always even.
4.8[GATE 2000 : 2 Marks] Let G be an undirected connected graph with distinct edge weights. Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false?
(a) Every minimum spanning tree of G must contain emin
(b) If emax is in a minimum spanning tree, then its removal must disconnect G
(c) No minimum spanning tree contains emax
(d) G has a unique minimum spanning tree
Solution:(a) True: emin is the lightest edge in whole graph, it will never form cycle alone, so Cut Property se har MST me aayega.(d) True: Distinct weights hai to MST unique hota hai.(b) True: Agar emax MST me hai aur woh bridge nahi hai, to usko hatake us cycle ki dusri lighter edge se replace kar sakte the. So agar woh MST me hai, iska matlab woh bridge hai, hatane se graph disconnect hoga.(c) False: Agar emax hi graph ka eklauta bridge hai jo 2 parts ko jod raha hai, to har MST ko usko lena hi padega, chahe kitna bhi heavy ho.Answer: (c) No minimum spanning tree contains emax is FALSE.
4.9[GATE 2001 : 2 Marks] How many undirected graphs (not necessary connected) can be constructed out of a given set V = { v1,v2,…..vn} of n vertices?
(a) n(n-1)/2 (b) 2n (c) n! (d) 2n(n−1)/2
Solution: Answer: (d) 2n(n−1)/2
n vertices pe maximum possible edges kitne?
Har pair se ek edge: nC2=n(n−1)/2Ab har edge ke liye 2 choice hai: lo ya mat lo.To total graphs = 2max edges=2n(n−1)/2
4.10[GATE 2002 : 1 Mark] Maximum number of edges in a n-node undirected graph without self loops is
(a) n2 (b) n(n-1)/2 (c) n-1 (d) (n+1)(n)/2
Solution: Answer: (b) n(n-1)/2
Without self loop, complete graph me max edges hota hai.Complete graph Kn me edges = n(n−1)/2Agar self-loop allowed hota to n(n+1)/2 ho jata.
4.11[GATE 2003 : 1 Mark] Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between.
(a) k and n
(b) k-1 and k+1
(c) k-1 and n-1
(d) k+1 and n-k
Solution:Answer: (c) k-1 and n-1
Vertex remove karne pe 2 extreme cases:Best case (minimum components): Agar jo vertex hata rahe ho woh akela isolated component tha, to k se 1 kam ho jayega. So minimum = k−1Worst case (maximum components): Agar vertex ek articulation point hai jo apne component ko bahut tukdo me baant de. Saare n−1 bache hue vertices alag-alag ho sakte hai. So maximum = n−1Isliye range k−1 se n−1 tak.
4.12[GATE 2003 : 2 Marks] How many perfect matchings are there in a complete graph of 6 vertices?
(a) 15 (b) 24 (c) 30 (d) 60
Solution: Answer: (a) 15
Complete graph Kn me perfect matching ka formula = (n−1)!!=(n−1)×(n−3)×…×1For n=6:
First vertex ko 5 choices, second bache hue ko 3 choices, last ke liye 1 choice.
Total = 5×3×1=15Formula se: 2n/2(n/2)!n!.
4.13 [GATE 2003 : 2 Marks]A Graph G = (V, E) satisfies |E| ≤ 3|V| – 6. The min-degree of G is defined as min {degree(v)}. Therefore, min-degree of G cannot be
(a) 3 (b) 4 (c) 5 (d) 6
Solution :Answer: (d) 6
Planar graph ka property hai e≤3v−6.Average degree = 2∣E∣/∣V∣≤2(3∣V∣−6)/∣V∣=6−12/∣V∣<6Matlab average degree hamesha 6 se kam hai.Agar min-degree 6 hota, to saare vertices ka degree >=6 hota, to average bhi >=6 hota, jo possible nahi hai.Isliye min-degree kabhi 6 nahi ho sakta. 0 to 5 tak ho sakta hai.
4.14[GATE 2004 2 Marks] The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is:
(a) 2
(b) 3
(c) 4
(d) 5
Solution: (c) 4
Figure me beech me 4 vertices hai jo ek cycle banate hai aur aapas me connected hai – isme K4 ka structure hai? Actually beech ke 4 vertices me 4-cycle + diagonals.Left wala outer vertex beech ke saare 4 se connected hai, right wala bhi 4 se connected hai.Left aur Right aapas me directly connected nahi hai, to unhe same colour diya ja sakta hai.Lekin beech ke 4 vertices ko alag-alag colours chahiye kyuki wo clique jaisa bana rahe hai. Check karne par chromatic number 4 aata hai.
4.15 [GATE 2004 : 2 Marks] How many graphs on n labeled vertices exist which have at least (n²-3n)/2 edges?
(a) (n2−n)/2C(n2−3n)/2
(b) ∑k=0(n2−3n)/2(n2−n)/2Ck
(c) (n2−n)/2Cn
(d) ∑k=0n(n2−n)/2Ck
Solution: Answer: (d) ∑k=0n(n2−n)/2Ck
Total possible edges in n labeled vertices = nC2=N=(n2−n)/2At least (n2−3n)/2 edges wale graphs =
NC(n2−3n)/2+NC(n2−3n)/2+1+…+NCNSymmetry se: NCr=NCN−rN−(n2−3n)/2=(n2−n−n2+3n)/2=nTo ye sum = NCN+NCN−1+…+NCN−n=NC0+NC1+…+NCnJo ki ∑k=0nNCk hai.
4.16 [GATE IT-2004 : 1 Mark] What is the maximum number of edges in an acyclic undirected graph with n vertices?
(a) n-1
(b) n
(c) n+1
(d) 2n-1
Solution: Answer: (a) n-1
Acyclic undirected graph matlab Forest. Agar connected hai to Tree.Tree me maximum edges = n−1 Cycle aate hi acyclic property khatam ho jayegi.
4.18 [GATE 2005 : 1 Mark]Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is
(a) 0
(b) 8
c) 9
(d) 13
Solution: Answer: (b) 8
Euler’s Formula for connected planar graph:
v−e+f=2
Given v=13, e=19
13−19+f=2
f=2+6=8
4.19[GATE 2005 : 2 Marks] Which one of the following graphs is NOT planar?
G1, G2, G3, G4 (see Figure)
Solution: Answer: (a) G1
G1: 6 vertices, andar cross edges hai jo K3,3 ka subdivision banate hai. Ye non-planar hai.G2, G3, G4 sab planar hai, unhe bina crossing ke draw kiya ja sakta hai.GATE ne G1 ko non-planar mana hai.
4.20[GATE IT-2006 : 1 Mark] If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum weight is a
(a) Hamiltonian cycle
(b) Grid
(c) Hypercube
(d) Tree
Solution: Answer: (d) Tree
Saare vertices ko connect karna hai aur weight minimum rakhna hai, aur saare weights positive hai.Agar cycle hoga to us cycle ka ek edge hatane se bhi graph connected rahega aur weight aur kam ho jayega. Isliye minimum wale set me cycle ho hi nahi sakta.Acyclic + connected = TreeYe hi Minimum Spanning Tree ki definition hai.
4.21[GATE IT-2006 : 2 Marks] Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is
(a) 1/(2n−1)
(b) 1/n
(c) 2/n
(d) 3/n
Solution: Answer: (c) 2/n.
Ye graph famous hai – n-dimensional Hypercube QnChromatic Number: Hypercube bipartite hota hai. Bit strings ko number of 1’s ke parity (even/odd) se 2 set me baant do. Edge hamesha even se odd me jayega. To 2 colours kaafi hai. χ(G)=2Diameter: Diameter = maximum shortest path. Hypercube me 2 opposite corners jaise 000…0 se 111…1 tak jaane ke liye n bits flip karne padenge. To diameter = nRatio = diameterχ(G)=n2