1
GATE CSE 2015 Set 2
MCQ (Single Correct Answer)
+2
-0.6
In a connected graph, bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
A
A tree has no bridges
B
A bridge cannot be part of a simple cycle
C
Every edge of a clique with size $$ \ge 3$$ is a bridge (A clique is any complete sub-graph of a graph )
D
A graph with bridges cannot have a cycle
2
GATE CSE 2014 Set 3
MCQ (Single Correct Answer)
+2
-0.6
If $$G$$ is a forest with $$n$$ vertices and $$k$$ connected components, how many edges does $$G$$ have?
A
$$\left\lfloor {n/k} \right\rfloor $$
B
$$\left\lceil {n/k} \right\rceil \,$$
C
$$n - k$$
D
$$n - k + 1$$
3
GATE CSE 2014 Set 3
MCQ (Single Correct Answer)
+2
-0.6
Let $$\delta $$ denote the minimum degree of a vertex in a graph. For all planar graphs on $$n$$ vertices with $$\delta \ge 3$$, which one of the following is TRUE?
A
In any planar embedding, the number of faces is at least $${n \over 2} + 2$$
B
In any planar embedding, the number of faces is less than $${n \over 2} + 2$$
C
There is a planar embedding in which the number of facess is less than $${n \over 2} + 2$$
D
There is a planar embedding in which the number of faces is at most $${n \over {\delta + 1}}$$
4
GATE CSE 2014 Set 1
Numerical
+2
-0
Consider an undirectional graph $$G$$ where self-loops are not allowed. The vertex set of $$G$$ is $$\left\{ {\left( {i,j} \right):\,1 \le i \le 12,\,1 \le j \le 12} \right\}.$$ There is an edge between $$(a,b)$$ and $$(c,d)$$ if $$\left| {a - c} \right| \le 1$$ and $$\left| {b - d} \right| \le 1$$. The number of edges in this graph is _____.
Your input ____
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP