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 viewed questions in Graph Theory

2 votes

2 answers

391

Graph Theory
consider the following statement-: 1.If a graph has Euler circuit then it is Strongly Connected graph. 2.If a graph has Euler path(but not Euler circuit) then it is Strongly Connected graph. 3.If a graph has Euler circuit then it is Weakly Connected ... .If a graph has Euler path(but not euler circuit) then it is Weakly Connected graph. Which statement is true with proper explanation.

consider the following statement-:1.If a graph has Euler circuit then it is Strongly Connected graph.2.If a graph has Euler path(but not Euler circuit) then it is Strongl...

sourav.

1.1k views

sourav. asked Aug 12, 2016

6 votes

2 answers

392

GO Classes 2023 | IIITH Mock Test 1 | Question: 3
Let $\text{G}$ be a graph on $10$ vertices. We delete one vertex from $\text{G}.$ Since we have $10$ vertices, hence we get $10$ different subgraphs depending on which vertex we have deleted. Suppose that the number of edges in the vertex-deleted subgraphs of ... $\text{G}?$ $14$ $16$ $13$ $15$

Let $\text{G}$ be a graph on $10$ vertices. We delete one vertex from $\text{G}.$ Since we have $10$ vertices, hence we get $10$ different subgraphs depending on which ve...

GO Classes

1.1k views

GO Classes asked Mar 26, 2023

0 votes

1 answer

393

graph theory

Vicky rix

1.1k views

Vicky rix asked Mar 12, 2017

4 votes

1 answer

394

GATE Overflow | Mock GATE | Test 1 | Question: 54
Let $S$ be a set of $n$ elements $\{1, 2, \dots n\}$ and $G$ a graph with $2^n$ vertices, where each vertex corresponds to a distinct subset of $S$. Two vertices are adjacent if the symmetric difference of the corresponding sets has exactly $2$ ... how many connected component does $G$ have, respectively? $n, 3$ $(n(n-1))/2,2$ $1, n$ $n+1, n$

Let $S$ be a set of $n$ elements $\{1, 2, \dots n\}$ and $G$ a graph with $2^n$ vertices, where each vertex corresponds to a distinct subset of $S$. Two vertices are adja...

Ruturaj Mohanty

1.1k views

Ruturaj Mohanty asked Dec 27, 2018

5 votes

2 answers

395

Graph Theory conceptual
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree ... a vertex of degree 7. Which of the following can be the degree of the last vertex? (A) 3 (B) 0 (C) 5 (D) 4

A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such tha...

Parshu gate

1.1k views

Parshu gate asked Nov 13, 2017

1 votes

4 answers

396

CMI2013-B-03
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least two vertices with the same degree.

A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least...

go_editor

1.1k views

go_editor asked May 23, 2016

2 votes

1 answer

397

Virtual Gate Test Series: Discrete Mathematics - Graph Theory
Consider the following two statements$:$ The two graphs $G_{1}$ and $G_{2}$ are isomorphic Each of $G_{1}$ and $G_{2}$ are self-dual. Both $(i)$ and $(ii)$ are true Only $(i)$ is true Only $(ii)$ is true Both $(i)$ and $(ii)$ are false

Consider the following two statements$:$The two graphs $G_{1}$ and $G_{2}$ are isomorphicEach of $G_{1}$ and $G_{2}$ are self-dual. Both $(i)$ and $(ii)$ are trueOnly $(i...

Prince Sindhiya

1.1k views

Prince Sindhiya asked Oct 15, 2018

0 votes

1 answer

398

Perfect Matching
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect matching will have n/2 edges and there won't be any perfect matching if n is ... t know whether i got it properly or not. Can please anybody explain the Perfect matching in a complete graph with simpler examples ?

Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect match...

Na462

1.1k views

Na462 asked Jun 10, 2018

1 votes

1 answer

399

please solve this Q
Q . The maximum number of edges in an undirected graph (simple) with 52 vertices and 3 components are

Q . The maximum number of edges in an undirected graph (simple) with 52 vertices and 3 components are

kallu singh

1.1k views

kallu singh asked Aug 8, 2017

1 votes

2 answers

400

CMI2016-A-1
In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following property: there exists a vertex that is a neighbour of all other vertices. Consider the following statements: If ... say about these statements? Only i is true Only ii is true Both i and ii are true Neither i nor ii is true

In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following proper...

go_editor

1.1k views

go_editor asked Dec 30, 2016

7 votes

2 answers

401

Graph connectivity
Consider the following statements $S1:2,3,3,3,3,3,4$ is a graphic sequence $S2:$ A connected graph with $10$ vertices and $16$ edges without having a cycle of length $3$, is a planar graph. Both $S1$ and $S2$ are true $S1$ is false but $S2$ is true $S2$ is false but $S1$ is true Both $S1$ and $S2$ are false

Consider the following statements$S1:2,3,3,3,3,3,4$ is a graphic sequence$S2:$ A connected graph with $10$ vertices and $16$ edges without having a cycle of length $3$, i...

Rahul Jain25

1.1k views

Rahul Jain25 asked Oct 10, 2016

0 votes

2 answers

402

self doubt
Both euler path and euler circuit can be present in a graph ?

Both euler path and euler circuit can be present in a graph ?

raja11sep

1.0k views

raja11sep asked Jan 5, 2022

0 votes

2 answers

403

CMI2017-A-04
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at ... number of edges. Find a spanning tree with minimum cost. Find a minimal coloring. Find a minimum size vertex cover.

City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of an...

Tesla!

1.0k views

Tesla! asked Feb 4, 2018

7 votes

1 answer

404

TIFR CSE 2012 | Part B | Question: 20
This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question. Let $L$ be a set. We say that $L$ is in $P$ if there is some algorithm which given input $x$ decides if ... $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$ none of the above

This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question.Let $L$ be a set. We say that...

Arjun

1.0k views

Arjun asked Nov 14, 2015

0 votes

2 answers

405

ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree-1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree-4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.

ACE Workbook:Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree-1,2 vertices of degree 2, 4 vertices of degree 3 and 3 ve...

chandan2teja

1.0k views

chandan2teja asked May 12, 2019

2 votes

2 answers

406

NIELIT Scientific Assistant A 2020 November: 19
What is the total number of ways to reach from $A$ to $B$ in the network given? $12$ $16$ $20$ $22$

What is the total number of ways to reach from $A$ to $B$ in the network given?$12$$16$$20$$22$

gatecse

1.0k views

gatecse asked Dec 8, 2020

4 votes

1 answer

407

GO Classes Scholarship 2023 | Test | Question: 8
In a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$, two nodes $u$ and $v$ are strongly connected if and only if they are mutually reachable i.e. there is a path from u to $v$ and a path from $v$ to $u$. ... connected components $\dots?$ can not increase can not decrease by more than $1$ can not decrease by more than $2$ may remain unchanged

In a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$, two nodes $u$ and $v$ are strongly connected if and only if they are mutually reachable i.e. there is a path fr...

GO Classes

1.0k views

GO Classes asked Aug 6, 2022

6 votes

1 answer

408

TIFR CSE 2020 | Part B | Question: 14
The figure below describes the network of streets in a city where Motabhai sells $\text{pakoras}$ from his cart. The number next to an edge is the time (in minutes) taken to traverse the corresponding street. At present, the cart is required to start at point $s$ ... $f$ are the only odd degree nodes in the figure above. $430$ $440$ $460$ $470$ $480$

The figure below describes the network of streets in a city where Motabhai sells $\text{pakoras}$ from his cart. The number next to an edge is the time (in minutes) taken...

admin

1.0k views

admin asked Feb 10, 2020

1 votes

1 answer

409

Degree Sequence
$<2, 2, 2, 1, 1>$ degree sequence is NOT graphic for simple graphs$?$

$<2, 2, 2, 1, 1>$ degree sequence is NOT graphic for simple graphs$?$

venkatesh456

1.0k views

venkatesh456 asked Sep 14, 2018

1 votes

1 answer

410

Graph theory and Applications Bondy and Murty Exercise Qn 1.9
A k partite graph is one where vertex set can be partitioned into k subsets so that no edge has both end in any one subset. A complete k partite graph is one that is simple and in which each vertex is joined to every other vertex that is not ... on n vertices then | E(G) | <= | E(Tm,n)|, with equality only if G isomorphic to Tm,n

A k partite graph is one where vertex set can be partitioned into k subsets so that no edge has both end in any one subset.A complete k partite graph is one that is simpl...

janakyMurthy

1.0k views

janakyMurthy asked May 9, 2017

Page:

« prev
1
...
15
16
17
18
19
20
21
22
23
24
25
...
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