Syllabus: Connectivity, Matching, Coloring.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}& \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} & 1&1&0&0&1&1&0&1&0&1&0&0.6&1
\\\hline\textbf{2 Marks Count} & 3 &1&0&1&1&1&0&0&0&0&0&0.7&3
\\\hline\textbf{Total Marks} & 7 &3&0&2&3&3&0&1&0&1&\bf{0}&\bf{2}&\bf{7}\\\hline
\end{array}}}$$

Most answered questions in Graph Theory

1 votes

3 answers

TIFR CSE 2020 | Part B | Question: 11
Which of the following graphs are bipartite? Only $(1)$ Only $(2)$ Only $(2)$ and $(3)$ None of $(1),(2),(3)$ All of $(1),(2),(3)$

Which of the following graphs are bipartite?Only $(1)$Only $(2)$Only $(2)$ and $(3)$None of $(1),(2),(3)$All of $(1),(2),(3)$

admin

3.5k views

admin asked Feb 10, 2020

6 votes

3 answers

CMI2018-A-4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$

Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ ...

gatecse

792 views

gatecse asked Sep 13, 2019

4 votes

3 answers

ACE ACADEMY BOOKLET QUESTION
Let $G$ $=$ $(V, E)$ be a simple non-empty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two non-empty and non-overlapping subsets $S$ and $T$. Which of the following is true? There are at least two edges that ... $S$ and one end point in $T$ There are exactly one edge that have one end point in $S$ and one end point in $T$

Let $G$ $=$ $(V, E)$ be a simple non-empty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two non-empty and non-overlapping su...

`JEET

1.2k views

`JEET asked May 26, 2019

2 votes

3 answers

Ace academy booklet #graph theory
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Euler circuit exists $\Leftrightarrow$ $n$ is odd. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Euler circuit exists ... Euler circuit exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Euler circuit exits $\Leftrightarrow$ $n$ is even.

Which of the following is $\textbf{not}$ TRUE?(a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Euler circuit exists $\Leftrightarrow$ $n$ is odd.(b) In a complete bipartit...

`JEET

1.9k views

`JEET asked May 26, 2019

2 votes

3 answers

Made easy Test Series:Graph Theory+Automata
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________

Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$,where each $...

srestha

944 views

srestha asked May 23, 2019

0 votes

3 answers

Doubt [Graph Theory]
Is it possible that a disconnected graph be an Euler graph ?

Is it possible that a disconnected graph be an Euler graph ?

jatin khachane 1

2.0k views

jatin khachane 1 asked Dec 24, 2018

2 votes

3 answers

Zeal Test Series 2019: Graph Theory - Graph Connectivity

Prince Sindhiya

925 views

Prince Sindhiya asked Dec 21, 2018

2 votes

3 answers

Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? Vertex $n$ has degree $1$ Graph is connected There is a path from vertex $1$ to vertex $n$ Spanning tree will include edge connecting vertex $1$ and vertex $n$

Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Wh...

Lakshman Bhaiya

1.2k views

Lakshman Bhaiya asked Oct 10, 2018

1 votes

3 answers

Doubt
For a complete graph with 10 vertices, The number of spanning trees is at least_____?

For a complete graph with 10 vertices, The number of spanning trees is at least_____?

Rishav Kumar Singh

979 views

Rishav Kumar Singh asked Aug 22, 2018

7 votes

3 answers

100

ISRO2018-38
The number of edges in a regular graph of degree: $d$ and $n$ vertices is: maximum of $n$ and $d$ $n +d$ $nd$ $nd/2$

The number of edges in a regular graph of degree: $d$ and $n$ vertices is:maximum of $n$ and $d$ $n +d$$nd$$nd/2$

Arjun

14.0k views

Arjun asked Apr 22, 2018

1 votes

3 answers

101

CMI2017-B-5
An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a connected, undirected graph that contains no cycle. A $\text{leaf}$ in a tree is a vertex that ... $ \in V_2$ or vice versa. Prove that if $G$ is a tree with at least two vertices, then $G$ is bipartite.

An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a co...

Tesla!

1.3k views

Tesla! asked Feb 5, 2018

3 votes

3 answers

102

Ace Test Series: Graph Theory - Number Of Spanning Trees
How to approach such questions ? Please provide detailed solution. Answer given is option C

How to approach such questions ? Please provide detailed solution. Answer given is option C

kapilbk1996

4.3k views

kapilbk1996 asked Feb 2, 2018

32 votes

3 answers

103

TIFR CSE 2018 | Part B | Question: 8
In an undirected graph $G$ with $n$ vertices, vertex $1$ has degree $1$, while each vertex $2,\ldots,n-1$ has degree $10$ and the degree of vertex $n$ is unknown, Which of the following statement must be TRUE on the graph $G$? There is a path ... Vertex $n$ has degree $1$. The diameter of the graph is at most $\frac{n}{10}$ All of the above choices must be TRUE

In an undirected graph $G$ with $n$ vertices, vertex $1$ has degree $1$, while each vertex $2,\ldots,n-1$ has degree $10$ and the degree of vertex $n$ is unknown, Which o...

Arjun

5.5k views

Arjun asked Dec 10, 2017

0 votes

3 answers

104

UGC NET CSE | June 2009 | Part 2 | Question: 23
Which two of the following are equivalent for an undirected graph G ? (i) G is a tree (ii) There is at least one path between any two distinct vertices of G (iii) G contains no cycles and has (n-1) edges (iv) G has n edges (i) and (ii) (i) and (iii) (i) and (iv) (ii) and (iii)

Which two of the following are equivalent for an undirected graph G ?(i) G is a tree(ii) There is at least one path between any two distinct vertices of G(iii) G contain...

rishu_darkshadow

4.7k views

rishu_darkshadow asked Sep 22, 2017

3 votes

3 answers

105

graph
Assume undirected graph G is connected . G has 6 vertices and 10 edges. Find the minimum number of edges whose deletion from graph G is always guaranteee that it will become disconnected

Assume undirected graph G is connected . G has 6 vertices and 10 edges. Find the minimum number of edges whose deletion from graph G is always guaranteee that it will bec...

A_i_$_h

3.8k views

A_i_$_h asked Sep 14, 2017

2 votes

3 answers

106

Kenneth Rosen Edition 7 Exercise 10.8 Question 23 (Page No. 734)
Find the edge chromatic numbers of a) Cn, where n ≥ 3. (Cycle with n vertices) b) Wn, where n ≥ 3 (Wheel with n vertices) c)Complete graph with n vertices.

Find the edge chromatic numbers ofa) Cn, where n ≥ 3. (Cycle with n vertices)b) Wn, where n ≥ 3 (Wheel with n vertices)c)Complete graph with n vertices.

Soumya29

3.7k views

Soumya29 asked Jul 8, 2017

3 votes

3 answers

107

[Discrete Maths] Graph Theory Rosen,Chromatic number
What are the chromatic number of following graphs? Answer is 6 and 4 respectively.But i am getting 3 for both. Please someone confirm this?

What are the chromatic number of following graphs?Answer is 6 and 4 respectively.But i am getting 3 for both.Please someone confirm this?

rahul sharma 5

2.0k views

rahul sharma 5 asked Jun 12, 2017

3 votes

3 answers

108

PGEE 2017
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y Find number of strongly connected components

Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yFind number of strongly connected com...

Tesla!

1.2k views

Tesla! asked Apr 30, 2017

3 votes

3 answers

109

graph theory
A graph consists of only one vertex,which is isolated ..Is that graph A) a complete graph ??? B) a clique??? C) connected graph ??? Please explain your answer ...

A graph consists of only one vertex,which is isolated ..Is that graphA) a complete graph ???B) a clique???C) connected graph ???Please explain your answer ...

Vicky rix

1.5k views

Vicky rix asked Apr 7, 2017

15 votes

3 answers

110

ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

Shreya Roy

2.4k views

Shreya Roy asked Apr 5, 2017

Page:

« prev
1
2
3
4
5
6
7
8
9
10
...
53
next »

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