Recent questions and answers in Graph Theory - GATE CSE Doubts

0 votes

0 answers

Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 4 Question 27

asked Jun 24 in Graph Theory by dararirum (7 points) | 13 views

0 votes

0 answers

Self doubt GRAPH THEORY

asked May 31 in Graph Theory by Abhipsa (27 points) | 11 views

0 votes

0 answers

Find no of Hamiltonian cycles in kn,n
How many Hamiltonian cycles are there in complete bipartite graph K n,n

asked May 9 in Graph Theory by SANDEEP1729 (7 points) | 4 views

0 votes

0 answers

Trees self doubt
S1: A tree with n vertices which has no vertices of degree 2 must have at least leaves S2: The number of trees on 5 labelled vertices is 125. Which of the following statements is true? (A). Only S1 (B). Only S2 (C). Only S1 and S2 (D). None of the above

asked May 8 in Graph Theory by Abhipsa (27 points) | 14 views

0 votes

0 answers

Hamiltonian Graph
Consider the following Graphs: S1: Graph with vertices and each vertex has degree S2: Graph with 20 vertices such that for every 2 vertices Which of the following represents hamilton graph? (A). Only S1 (B). Only S2 (C). Both S1 and S2 (D). Neither S1 nor S2

asked May 8 in Graph Theory by Abhipsa (27 points) | 5 views

0 votes

0 answers

adjacency matrix in graphs
A represents an adjacency matrix of Graph G The number of paths of length 8 from vertex 1 to vertex 4??

asked May 8 in Graph Theory by Abhipsa (27 points) | 12 views

0 votes

0 answers

Matching Number
Please tell me what is the Independence Number Domination Number Matching Number Covering Number of the given graph in the picture. Does perfect matching exist in the given graph?

asked May 7 in Graph Theory by Abhipsa (27 points) | 15 views

0 votes

0 answers

Graph theory 3-Ordered trees possible for a given no of nodes

asked Apr 28 in Graph Theory by ramcharantej_24 (22 points) | 7 views

0 votes

0 answers

Number of perfect matching in Kn?
Find number of perfect matching in Kn where n is even? Please explain too?

asked Apr 23 in Graph Theory by darshansharma_ (13 points) | 4 views

0 votes

0 answers

Why Euler circuit does not exist when number of odd degree vertices is 2

asked Apr 23 in Graph Theory by darshansharma_ (13 points) | 10 views

0 votes

0 answers

What is the degree of region?
What is the degree of region r4? How you find it?

asked Apr 22 in Graph Theory by darshansharma_ (13 points) | 4 views

0 votes

0 answers

Proof of Euler equation
Euler equation is - |V| +|R| = |E| + 2 Can someone please show me how to come to above conclusion?

asked Apr 22 in Graph Theory by darshansharma_ (13 points) | 2 views

0 votes

0 answers

GATE2012-38 Video Solution
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

GATE1994-1.6, ISRO2008-29 Video Solution
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

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______.

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2018-30 Video Solution
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is ... $\mid i-j \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

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

asked Apr 19 in Graph Theory by admin (3.6k points) | 3 views

0 votes

0 answers

GATE2002-1.25, ISRO2008-30, ISRO2016-6 Video Solution

asked Apr 19 in Graph Theory by admin (3.6k points) | 8 views

0 votes

0 answers

GATE2003-36 Video Solution
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2016-2-03 Video Solution
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2006-71 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 vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2007-IT-25 Video Solution
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

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

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

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$

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2010-28 Video Solution
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

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2006-72 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 maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n-2}$ $2^{n-3}\times 3$ $2^{n-1}$

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

GATE1994-2.5 Video Solution
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2014-2-3 Video Solution
The maximum number of edges in a bipartite graph on $12$ vertices is____

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2017-2-23 Video Solution
$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 _________ .

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2013-26 Video Solution
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 $e$ and ... of a 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

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2004-79 Video Solution
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$

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

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$

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

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}$

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

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

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2001-2.15 Video Solution
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} $

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2003-40 Video Solution
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$

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2014-2-51 Video Solution
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1991-01,xv Video Solution
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.

asked Apr 19 in Graph Theory by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2009-2 Video Solution
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$

asked Apr 19 in Graph Theory by admin (3.6k points) | 4 views

0 votes

0 answers

GATE2010-1 Video Solution
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$

asked Apr 19 in Graph Theory by admin (3.6k points) | 1 view

To see more, click for all the questions in this category.

Recent questions and answers in Graph Theory

7,525 questions

1,777 answers

10,838 comments

90,464 users