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

Hot questions in Graph Theory

0 votes

1 answer

391

Self doubt
Is this graph Euler?

Is this graph Euler?

Shadan Karim

430 views

Shadan Karim asked Dec 21, 2018

0 votes

0 answers

392

Aai 2018 it

Shashi Shekhar 1

577 views

Shashi Shekhar 1 asked Dec 10, 2018

0 votes

0 answers

393

ME Test Series

Shadan Karim

258 views

Shadan Karim asked Dec 23, 2018

0 votes

1 answer

394

#tree
What is the number of spanning tree in cyclic graph

What is the number of spanning tree in cyclic graph

Sumita Bose

296 views

Sumita Bose asked Dec 20, 2018

0 votes

0 answers

395

VirtualGate Graph Question
The degree sequence of a graph $G$ is $\text{2, 2, 2, 3, 3, 3, 3, 5}$. The ratio $2|E|/|V|$ ranges 2, 5 3, 5 2, 3 None I tried to find out wether this degree sequence correspond to some graph or not. But its not a graphical sequence. Please verify it once and if its a correct graphical sequence then what would be the correct answer for this?

The degree sequence of a graph $G$ is $\text{2, 2, 2, 3, 3, 3, 3, 5}$. The ratio $2|E|/|V|$ ranges2, 53, 52, 3NoneI tried to find out wether this degree sequence correspo...

!KARAN

454 views

!KARAN asked Dec 8, 2018

3 votes

1 answer

396

Graph Coloring
A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below graphs: The number of vertex colouring possible with 4 colours are _________.

A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below gr...

srestha

2.0k views

srestha asked Sep 21, 2018

1 votes

1 answer

397

EET IITD

Churchill Khangar

618 views

Churchill Khangar asked Nov 23, 2018

0 votes

0 answers

398

Let T = (V, E) be a tree, where V is the vertex set and E is the edge set. If |E| = 25, then |V |

venkatesh456

1.3k views

venkatesh456 asked Sep 14, 2018

2 votes

1 answer

399

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

0 answers

400

Graph Theory(Eular walk)
$A)$ If a graph has closed Eularian walk, then it has an even number of edges $B)$ If $G$ be a simple graph on $9$ vertices and the sum of all degrees in $G$ is atleast $27$, then $G$ has a vertex of degree atleast $4$. Which Statement should be true? Is it possible B) to be true? And for A) I think "only if" is needed in place of "if" to be true

$A)$ If a graph has closed Eularian walk, then it has an even number of edges$B)$ If $G$ be a simple graph on $9$ vertices and the sum of all degrees in $G$ is atleast $2...

srestha

847 views

srestha asked Nov 16, 2018

0 votes

1 answer

401

DSA-Test 3-Question 9
Consider following statements: (i) Every simple graph has at least two vertices of the same degree. (ii) If u is a vertex of odd degree in a graph, then there exists a path from u to another vertex v of the graph where v also has odd degree. (iii) If there are exactly ... above statements are not true? (A) (i) and (ii) only (B) (iii) only (C) (ii) only (D) None of the above

Consider following statements: (i) Every simple graph has at least two vertices of the same degree. (ii) If u is a vertex of odd degree in a graph, then there exists a pa...

Sandy Sharma

1.5k views

Sandy Sharma asked Sep 18, 2018

0 votes

0 answers

402

Regular Graph
If a 2-regular graph G has a perfect matching then which of the following is/are true? S1: G is a cycle of even length S2: Chromatic number of G is 2 S3: G is connected S4: Every component of G is an even cycle Options- A) S1,S2 B)S2,S4 C)S3,S4 D)S1,S4

If a 2-regular graph G has a perfect matching then which of the following is/are true? S1: G is a cycle of even length S2: Chromatic number of G is 2 S3: G is co...

dan31

901 views

dan31 asked Nov 6, 2018

6 votes

3 answers

403

How to find no of paths of length 2 in the below graph ?
Determine the number of paths of length $2$ in the following graph I couldn't get this logic .

Determine the number of paths of length $2$ in the following graphI couldn't get this logic .

radha gogia

4.9k views

radha gogia asked Nov 28, 2015

11 votes

2 answers

404

ISI2015-PCB-C3
For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n$-bit binary strings and $E = \{(u,v) \mid u, v$ belongs to $V, u$ and $v$ differ in exactly one bit position$\}$. Determine size of $E$ Show that $G$ is connected

For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n...

Devasish Ghosh

1.5k views

Devasish Ghosh asked Mar 8, 2017

0 votes

0 answers

405

ACE Testseries
Minimum number of cables required to connect 8 computers to 4 printers to ensure that any 4 computers can directly access 4 different printers is

Minimum number of cables required to connect 8 computers to 4 printers to ensure that any 4 computers can directly access 4 different printers is

Vipin Rai

445 views

Vipin Rai asked Nov 30, 2018

1 votes

0 answers

406

Graph theory

Deepalitrapti

979 views

Deepalitrapti asked Oct 24, 2018

3 votes

2 answers

407

Number of Subgraphs of Kn?
I was searching for this question and found below link How many subgraphs does $K_5$ have? Here, in general, it is given to be $\displaystyle\sum_{r=0}^{n}\binom{n}{r}2^{\frac{r(r-1)}{2}}$ My doubt is that the case for $r=0$ is taken if we select none of the vertices of $K_n$? Why the case for $ r=0$ considered?

I was searching for this question and found below linkHow many subgraphs does $K_5$ have?Here, in general, it is given to be$\displaystyle\sum_{r=0}^{n}\binom{n}{r}2^{\fr...

Ayush Upadhyaya

2.9k views

Ayush Upadhyaya asked Jun 5, 2018

1 votes

1 answer

408

Test Series
Let K$_n$ be such that the vertices are labeled 1,2,3,...n. The number of simple paths between v$_1$ and v$_n$ such that the labels on the path are strictly increasing ____________________

Let K$_n$ be such that the vertices are labeled 1,2,3,...n.The number of simple paths between v$_1$ and v$_n$ such that the labels on the path are strictly increasing ___...

Gupta731

799 views

Gupta731 asked Oct 29, 2018

0 votes

1 answer

409

Bipartite graph
The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the same color?

The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the ...

Lakshman Bhaiya

1.2k views

Lakshman Bhaiya asked Oct 10, 2018

0 votes

1 answer

410

NIELIT 2017 DEC Scientist B - Section B: 23
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to: $15$ $30$ $56$ $60$

Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to:$15$$30$$56$$...

admin

2.4k views

admin asked Mar 30, 2020

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