Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Graph Theory:
Recent questions tagged graph-theory
79
votes
12
answers
841
GATE CSE 1994 | Question: 1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
The number of distinct simple graphs with up to three nodes is$15$$10$$7$$9$
Kathleen
35.2k
views
Kathleen
asked
Oct 4, 2014
Graph Theory
gate1994
graph-theory
graph-connectivity
combinatory
normal
isro2008
counting
+
–
26
votes
4
answers
842
GATE CSE 1993 | Question: 8.1
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
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 cyclesThe graph obtained by re...
Kathleen
10.0k
views
Kathleen
asked
Sep 29, 2014
Graph Theory
gate1993
graph-theory
graph-connectivity
easy
multiple-selects
+
–
45
votes
6
answers
843
GATE CSE 1997 | Question: 6.2
Let $G$ be the graph with $100$ vertices numbered $1$ to $100$. Two vertices $i$ and $j$ are adjacent if $\vert i-j \vert =8$ or $\vert i-j \vert=12$. The number of connected components in $G$ is $8$ $4$ $12$ $25$
Let $G$ be the graph with $100$ vertices numbered $1$ to $100$. Two vertices $i$ and $j$ are adjacent if $\vert i-j \vert =8$ or $\vert i-j \vert=12$. The number of con...
Kathleen
9.2k
views
Kathleen
asked
Sep 29, 2014
DS
gate1997
data-structures
normal
graph-theory
+
–
17
votes
2
answers
844
GATE CSE 2011 | Question: 17
K4 and Q3 are graphs with the following structures. Which one of the following statements is TRUE in relation to these graphs? K4 is a planar while Q3 is not Both K4 and Q3 are planar Q3 is planar while K4 is not Neither K4 nor Q3 is planar
K4 and Q3 are graphs with the following structures.Which one of the following statements is TRUE in relation to these graphs?K4 is a planar while Q3 is notBoth K4 and Q3 ...
go_editor
7.1k
views
go_editor
asked
Sep 29, 2014
Graph Theory
gatecse-2011
graph-theory
graph-planarity
normal
+
–
19
votes
2
answers
845
GATE CSE 2014 Set 3 | Question: 52
Let $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \geq 3$, which one of the following is TRUE? In any planar embedding, the number of faces is at least $\frac{n}{2}+2$ In any planar ... than $\frac{n}{2}+2$ There is a planar embedding in which the number of faces is at most $\frac {n}{\delta+1}$
Let $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \geq 3$, which one of the following is TRUE?In any plana...
go_editor
8.2k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set3
graph-theory
graph-planarity
normal
+
–
57
votes
11
answers
846
GATE CSE 2014 Set 3 | Question: 51
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$
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\r...
go_editor
18.6k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set3
graph-theory
graph-connectivity
normal
+
–
42
votes
6
answers
847
GATE CSE 2014 Set 2 | Question: 51
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
go_editor
17.7k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set2
graph-theory
numerical-answers
normal
graph-isomorphism
non-gate
+
–
39
votes
9
answers
848
GATE CSE 2014 Set 2 | Question: 3
The maximum number of edges in a bipartite graph on $12$ vertices is____
The maximum number of edges in a bipartite graph on $12$ vertices is____
go_editor
27.3k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set2
graph-theory
graph-connectivity
numerical-answers
normal
+
–
36
votes
4
answers
849
GATE CSE 2014 Set 1 | Question: 52
An ordered $n-$tuple $(d_1, d_2,\ldots,d_n)$ with $d_1 \geq d_2 \geq \ldots \geq d_n$ is called graphic if there exists a simple undirected graph with $n$ vertices having degrees $d_1,d_2,\ldots,d_n$ respectively. Which one of the following $6$-tuples is NOT graphic? $(1,1,1,1,1,1)$ $(2,2,2,2,2,2)$ $(3,3,3,1,0,0)$ $(3,2,1,1,1,0)$
An ordered $n-$tuple $(d_1, d_2,\ldots,d_n)$ with $d_1 \geq d_2 \geq \ldots \geq d_n$ is called graphic if there exists a simple undirected graph with $n$ vertices havin...
go_editor
7.6k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set1
graph-theory
normal
degree-of-graph
+
–
103
votes
10
answers
850
GATE CSE 2014 Set 1 | Question: 51
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______.
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 $...
go_editor
27.1k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set1
graph-theory
numerical-answers
normal
graph-connectivity
+
–
66
votes
4
answers
851
GATE CSE 2006 | Question: 71
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 vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
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 set...
Rucha Shelke
17.5k
views
Rucha Shelke
asked
Sep 26, 2014
Graph Theory
gatecse-2006
graph-theory
normal
degree-of-graph
+
–
55
votes
3
answers
852
GATE CSE 2014 Set 1 | Question: 3
Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected components as $G$ ? $G_1$ = $(V,E_1)$ ... $u$ to $v$ in $E\}$ $G_4$ = $(V_4,E)$ where $V_4$ is the set of vertices in $G$ which are not isolated
Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected compon...
go_editor
17.1k
views
go_editor
asked
Sep 26, 2014
DS
gatecse-2014-set1
data-structures
graph-theory
ambiguous
+
–
29
votes
4
answers
853
GATE CSE 2012 | Question: 26
Which of the following graphs is isomorphic to
Which of the following graphs is isomorphic to
Arjun
11.2k
views
Arjun
asked
Sep 25, 2014
Graph Theory
gatecse-2012
graph-theory
graph-isomorphism
normal
non-gate
+
–
60
votes
8
answers
854
GATE CSE 2013 | Question: 26
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if ... planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only
The line graph $L(G)$ of a simple graph $G$ is defined as follows:There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$.For any two edges $e$ and $e'$ in ...
Arjun
19.3k
views
Arjun
asked
Sep 24, 2014
Graph Theory
gatecse-2013
graph-theory
normal
graph-connectivity
+
–
25
votes
2
answers
855
GATE CSE 2013 | Question: 25
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even. P only Q only Both P and Q Neither P nor Q
Which of the following statements is/are TRUE for undirected graphs?P: Number of odd degree vertices is even.Q: Sum of degrees of all vertices is even. P only Q only Both...
Arjun
16.1k
views
Arjun
asked
Sep 24, 2014
Graph Theory
gatecse-2013
graph-theory
easy
degree-of-graph
+
–
33
votes
5
answers
856
GATE CSE 1999 | Question: 5
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 ... $n$ vertices has a min-cut of cardinality $k$, then $G$ has at least $\left(\frac{n\times k}{2}\right)$ edges.
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 wi...
Kathleen
6.5k
views
Kathleen
asked
Sep 23, 2014
Graph Theory
gate1999
graph-theory
graph-connectivity
normal
descriptive
proof
+
–
39
votes
5
answers
857
GATE CSE 1999 | Question: 1.15
The number of articulation points of the following graph is $0$ $1$ $2$ $3$
The number of articulation points of the following graph is$0$$1$$2$$3$
Kathleen
9.0k
views
Kathleen
asked
Sep 23, 2014
Graph Theory
gate1999
graph-theory
graph-connectivity
normal
+
–
77
votes
5
answers
858
GATE CSE 2007 | Question: 23
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
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...
Kathleen
25.6k
views
Kathleen
asked
Sep 21, 2014
Graph Theory
gatecse-2007
graph-theory
normal
graph-connectivity
+
–
19
votes
3
answers
859
GATE CSE 2007 | Question: 4
Let $G$ be the non-planar graph with the minimum possible number of edges. Then $G$ has 9 edges and 5 vertices 9 edges and 6 vertices 10 edges and 5 vertices 10 edges and 6 vertices
Let $G$ be the non-planar graph with the minimum possible number of edges. Then $G$ has9 edges and 5 vertices9 edges and 6 vertices10 edges and 5 vertices10 edges and 6 v...
Kathleen
10.3k
views
Kathleen
asked
Sep 21, 2014
Graph Theory
gatecse-2007
graph-theory
normal
out-of-syllabus-now
+
–
16
votes
2
answers
860
GATE CSE 2005 | Question: 47
Which one of the following graphs is NOT planar? G1 G2 G3 G4
Which one of the following graphs is NOT planar? G1G2G3G4
gatecse
8.4k
views
gatecse
asked
Sep 21, 2014
Graph Theory
gatecse-2005
graph-theory
graph-planarity
normal
+
–
39
votes
4
answers
861
GATE CSE 2005 | Question: 11
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$
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:$1...
gatecse
12.0k
views
gatecse
asked
Sep 21, 2014
Graph Theory
gatecse-2005
graph-theory
normal
graph-connectivity
+
–
19
votes
3
answers
862
GATE CSE 2005 | Question: 10
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: $6$ $8$ $9$ $13$
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:$6$$8$$9$$13$
gatecse
9.3k
views
gatecse
asked
Sep 21, 2014
Graph Theory
gatecse-2005
graph-theory
graph-planarity
+
–
40
votes
7
answers
863
GATE CSE 2010 | Question: 28
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$ I and II III and IV IV only II and IV
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree...
gatecse
18.7k
views
gatecse
asked
Sep 21, 2014
Graph Theory
gatecse-2010
graph-theory
degree-of-graph
+
–
51
votes
5
answers
864
GATE CSE 2010 | Question: 1
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with $\xi(S) = \xi(T)$, then $| S| = 2| T |$ $| S | = | T | - 1$ $| S| = | T | $ $| S | = | T| + 1$
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with ...
gatecse
11.6k
views
gatecse
asked
Sep 21, 2014
Graph Theory
gatecse-2010
graph-theory
normal
degree-of-graph
+
–
55
votes
11
answers
865
GATE CSE 2004 | Question: 81
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cut-edge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected gr...
Kathleen
12.0k
views
Kathleen
asked
Sep 18, 2014
Graph Theory
gatecse-2004
graph-theory
normal
graph-connectivity
+
–
86
votes
8
answers
866
GATE CSE 2004 | Question: 79
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k$ $^{\left(\frac{n^2-n}{2}\right)}C_n$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ?$^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$$^{{\l...
Kathleen
14.6k
views
Kathleen
asked
Sep 18, 2014
Graph Theory
gatecse-2004
graph-theory
combinatory
normal
counting
+
–
37
votes
7
answers
867
GATE CSE 2004 | Question: 77
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is $2$ $3$ $4$ $5$
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is$2$$3$$4$$5$
Kathleen
12.9k
views
Kathleen
asked
Sep 18, 2014
Graph Theory
gatecse-2004
graph-theory
graph-coloring
easy
+
–
65
votes
9
answers
868
GATE CSE 2003 | Question: 40
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-degree of $G$ cannot be $3$ $4$ $5$ $6$
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-d...
Kathleen
15.9k
views
Kathleen
asked
Sep 17, 2014
Graph Theory
gatecse-2003
graph-theory
normal
degree-of-graph
+
–
61
votes
10
answers
869
GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$
Kathleen
50.7k
views
Kathleen
asked
Sep 16, 2014
Graph Theory
gatecse-2003
graph-theory
graph-matching
normal
+
–
66
votes
5
answers
870
GATE CSE 2003 | Question: 8, ISRO2009-53
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{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$
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must neces...
Kathleen
15.5k
views
Kathleen
asked
Sep 16, 2014
Graph Theory
gatecse-2003
graph-theory
graph-connectivity
normal
isro2009
+
–
Page:
« prev
1
...
24
25
26
27
28
29
30
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register