Recent questions tagged graph-connectivity
Register

Recent questions tagged graph-connectivity

Recent questions tagged graph-connectivity
0 votes
0 answers 16 views
#testsseries
Consider the following graph: Which of the following statements are false? A.There is no cycle in the above graph. B.There are exactly 3 back edges for a given DFS tree in the graph. C.There is atleast one strongly connected component present in the graph. D.The graph has a topological sort.
Abhishek tarpara asked in DS Aug 18, 2021
by Abhishek tarpara
13 points
16 views
0 votes
0 answers 720 views
GATE CSE 2021 Set 1 | Question: 36 | Video Solution
Arjun asked in Graph Theory Feb 18, 2021
by Arjun
1.4k points
720 views
0 votes
0 answers 25 views
GATE2014-1-51 Video Solution
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
25 views
0 votes
0 answers 25 views
GATE2018-43 Video Solution
Let $G$ be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent numbers ... denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____
admin asked in Algorithms Apr 18, 2020
by admin
589 points
25 views
0 votes
0 answers 24 views
GATE2007-23 Video Solution
Which of the following graphs has an Eulerian circuit? Any $k$-regular graph where $k$ is an even number. A complete graph on $90$ vertices. The complement of a cycle on $25$ vertices. None of the above
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
24 views
0 votes
0 answers 33 views
GATE2002-1.25, ISRO2008-30, ISRO2016-6 Video Solution
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
33 views
0 votes
0 answers 21 views
GATE1995-1.25 Video Solution
The minimum number of edges in a connected cyclic graph on $n$ vertices is: $n-1$ $n$ $n+1$ None of the above
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
21 views
0 votes
0 answers 29 views
GATE2014-3-51 Video Solution
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $n-k$ $n-k+1$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
29 views
0 votes
0 answers 23 views
GATE1994-2.5 Video Solution
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
23 views
0 votes
0 answers 21 views
GATE2014-2-3 Video Solution
The maximum number of edges in a bipartite graph on $12$ vertices is____
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
21 views
0 votes
0 answers 18 views
GATE2003-8, ISRO2009-53 Video Solution
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 down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
18 views
0 votes
0 answers 24 views
GATE2019-12 Video Solution
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
24 views
0 votes
0 answers 32 views
GATE2019-38 Video Solution
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
32 views
0 votes
0 answers 29 views
GATE1991-01,xv Video Solution
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
29 views
0 votes
0 answers 36 views
GATE2015-2-50 Video Solution
In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is true? A tree has no bridges A bridge cannot be part of a simple cycle Every edge of a clique with size $\geq 3$ is a bridge (A clique is any complete subgraph of a graph) A graph with bridges cannot have cycle
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
36 views
0 votes
0 answers 24 views
GATE2005-IT-56 Video Solution
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is $4$ $7$ $23$ $99$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
24 views
0 votes
0 answers 14 views
GATE2005-11 Video Solution
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is: $12$ $8$ less than $8$ more than $12$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
14 views
0 votes
0 answers 17 views
GATE2006-73 Video Solution
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
17 views
0 votes
0 answers 31 views
GATE2008-IT-27 Video Solution
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph is sure to be regular complete Hamiltonian Euler
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
31 views
0 votes
0 answers 14 views
GATE2004-IT-5 Video Solution
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
14 views
0 votes
0 answers 19 views
GATE2006-IT-11 Video Solution
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
19 views
0 votes
0 answers 61 views
GATE1999-1.15 Video Solution
The number of articulation points of the following graph is $0$ $1$ $2$ $3$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
61 views
0 votes
0 answers 18 views
GATE2004-IT-37 Video Solution
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$? $10$ $11$ $18$ $19$
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
18 views
0 votes
0 answers 26 views
GATE1993-8.1 Video Solution
Consider a simple connected graph $G$ with $n$ vertices and $n$ edges $(n > 2)$. Then, which of the following statements are true? $G$ has no cycles The graph obtained by removing any edge from $G$ is not connected $G$ has at least one cycle The graph obtained by removing any two edges from $G$ is not connected None of the above
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
26 views
0 votes
0 answers 36 views
GATE1999-5 Video Solution
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 ... $n$ vertices has a min-cut of cardinality $k$, then $G$ has at least $\left(\frac{n\times k}{2}\right)$ edges.
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
36 views
0 votes
0 answers 22 views
GATE1990-1-viii Video Solution
Fill in the blanks: A graph which has the same number of edges as its complement must have number of vertices congruent to ________ or ________ modulo $4$.
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
22 views
0 votes
0 answers 21 views
GATE1988-2xvi Video Solution
Write the adjacency matrix representation of the graph given in below figure.
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
21 views
0 votes
0 answers 18 views
GATE1987-9d Video Solution
Specify an adjacency-lists representation of the undirected graph given above.
admin asked in Graph Theory Apr 18, 2020
by admin
589 points
18 views
To see more, click for the full list of questions or popular tags.
Ask a Question
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Developed by Chun