Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for graph-theory
65
votes
9
answers
21
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.6k
views
Kathleen
asked
Sep 17, 2014
Graph Theory
gatecse-2003
graph-theory
normal
degree-of-graph
+
–
59
votes
8
answers
22
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.0k
views
Arjun
asked
Sep 24, 2014
Graph Theory
gatecse-2013
graph-theory
normal
graph-connectivity
+
–
65
votes
5
answers
23
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.4k
views
Kathleen
asked
Sep 16, 2014
Graph Theory
gatecse-2003
graph-theory
graph-connectivity
normal
isro2009
+
–
53
votes
6
answers
24
GATE CSE 2001 | Question: 2.15
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2} $
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices?$\frac{n(n-1)} {2}$$2^n$$n!$$2^\f...
Kathleen
14.1k
views
Kathleen
asked
Sep 14, 2014
Graph Theory
gatecse-2001
graph-theory
normal
counting
+
–
14
votes
3
answers
25
GATE CSE 2022 | Question: 27
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of $\textit{A}^{3}$ $\textit{A}^{3}$ divided by $2$ $\textit{A}^{3}$ divided by $3$ $\textit{A}^{3}$ divided by $6$
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the g...
Arjun
7.5k
views
Arjun
asked
Feb 15, 2022
Graph Theory
gatecse-2022
graph-theory
graph-connectivity
2-marks
+
–
64
votes
9
answers
26
GATE IT 2006 | Question: 25
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 ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
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 ...
Ishrat Jahan
13.2k
views
Ishrat Jahan
asked
Oct 31, 2014
Graph Theory
gateit-2006
graph-theory
graph-coloring
normal
+
–
7
votes
3
answers
27
GATE CSE 2023 | Question: 45
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices ... $\Delta(G)$. The number of colors used is equal to the chromatic number of $G$.
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=...
admin
8.3k
views
admin
asked
Feb 15, 2023
Graph Theory
gatecse-2023
graph-theory
graph-coloring
multiple-selects
2-marks
+
–
44
votes
9
answers
28
GATE CSE 2017 Set 2 | Question: 23
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
Madhav
17.5k
views
Madhav
asked
Feb 14, 2017
Graph Theory
gatecse-2017-set2
graph-theory
numerical-answers
degree-of-graph
+
–
39
votes
8
answers
29
GATE CSE 2002 | Question: 1.25, ISRO2008-30, ISRO2016-6
The maximum number of edges in a $n$-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$
Kathleen
18.7k
views
Kathleen
asked
Sep 15, 2014
Graph Theory
gatecse-2002
graph-theory
easy
isro2008
isro2016
graph-connectivity
+
–
49
votes
11
answers
30
GATE CSE 2009 | Question: 2
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n 2$.$2$$3$$n-1$ $n$
gatecse
13.2k
views
gatecse
asked
Sep 15, 2014
Graph Theory
gatecse-2009
graph-theory
graph-coloring
normal
+
–
37
votes
7
answers
31
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.7k
views
Kathleen
asked
Sep 18, 2014
Graph Theory
gatecse-2004
graph-theory
graph-coloring
easy
+
–
51
votes
4
answers
32
GATE CSE 1991 | Question: 01,xv
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
Kathleen
11.6k
views
Kathleen
asked
Sep 12, 2014
Graph Theory
gate1991
graph-theory
graph-connectivity
normal
fill-in-the-blanks
+
–
19
votes
5
answers
33
GATE CSE 2022 | Question: 20
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .
Arjun
8.8k
views
Arjun
asked
Feb 15, 2022
Graph Theory
gatecse-2022
numerical-answers
graph-theory
graph-connectivity
1-mark
+
–
54
votes
7
answers
34
GATE CSE 2009 | Question: 3
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices ...
gatecse
11.4k
views
gatecse
asked
Sep 15, 2014
Graph Theory
gatecse-2009
graph-theory
normal
degree-of-graph
+
–
16
votes
3
answers
35
number of perfect matching in complete graph
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
dhingrak
10.8k
views
dhingrak
asked
Dec 2, 2014
Graph Theory
discrete-mathematics
graph-theory
graph-matching
+
–
16
votes
4
answers
36
GATE CSE 2022 | Question: 42
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices? The diagonal entries of $A^{2}$ ... . If there is at least a $1$ in each of $A\text{'s}$ rows and columns, then the graph must be connected.
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?The diagonal entries of $A^{2}$ are the degrees of t...
Arjun
7.4k
views
Arjun
asked
Feb 15, 2022
Graph Theory
gatecse-2022
graph-theory
graph-connectivity
multiple-selects
2-marks
+
–
51
votes
5
answers
37
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.5k
views
gatecse
asked
Sep 21, 2014
Graph Theory
gatecse-2010
graph-theory
normal
degree-of-graph
+
–
2
votes
2
answers
38
GATE CSE 2024 | Set 2 | Question: 7
Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following statements is always TRUE? $\text{G}$ is a cycle $\text{G}$ is a perfect matching $\text{G}$ is a complete graph There is no such graph $\text{G}$
Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following statements i...
Arjun
2.8k
views
Arjun
asked
Feb 16
Graph Theory
gatecse2024-set2
graph-theory
+
–
46
votes
6
answers
39
GATE CSE 2002 | Question: 1.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is$2$$3$$4$$n-2 \lef...
Kathleen
11.2k
views
Kathleen
asked
Sep 15, 2014
Graph Theory
gatecse-2002
graph-theory
graph-coloring
normal
+
–
1
votes
3
answers
40
GATE CSE 2024 | Set 2 | Question: 50
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.
Arjun
1.9k
views
Arjun
asked
Feb 16
Graph Theory
gatecse2024-set2
graph-theory
numerical-answers
+
–
Page:
« prev
1
2
3
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register