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

38 votes

4 answers

TIFR CSE 2017 | Part B | Question: 1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$

A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the f...

go_editor

4.6k views

go_editor asked Dec 23, 2016

15 votes

4 answers

GATE CSE 1988 | Question: 2xvi
Write the adjacency matrix representation of the graph given in below figure.

Write the adjacency matrix representation of the graph given in below figure.

go_editor

4.0k views

go_editor asked Dec 19, 2016

31 votes

4 answers

GATE CSE 1989 | Question: 3-vi
Which of the following graphs is/are planar?

Which of the following graphs is/are planar?

makhdoom ghaya

7.8k views

makhdoom ghaya asked Nov 27, 2016

1 votes

4 answers

UGC NET CSE | December 2013 | Part 2 | Question: 39
A graph is non-planar if and only if it contains a subgraph homomorphic to $K_{3,2} \text{ or } K_5$ $K_{3,3} \text{ or } K_6$ $K_{3,3} \text{ or } K_5$ $K_{2,3} \text{ or } K_5$

A graph is non-planar if and only if it contains a subgraph homomorphic to$K_{3,2} \text{ or } K_5$$K_{3,3} \text{ or } K_6$$K_{3,3} \text{ or } K_5$$K_{2,3} \text{ or } ...

go_editor

4.0k views

go_editor asked Jul 26, 2016

11 votes

4 answers

ISRO2016-5
A given connected graph $\text{G}$ is a Euler Graph if and only if all vertices of $\text{G}$ are of same degree even degree odd degree different degree

A given connected graph $\text{G}$ is a Euler Graph if and only if all vertices of $\text{G}$ are ofsame degree even degreeodd degree ...

asu

9.1k views

asu asked Jul 4, 2016

1 votes

4 answers

IISC-CSA-Research-Test-10
A proper vertex colouring of a graph $G$ is a colouring of the vertices in $G$ in such a way that two vertices get different colours if they are adjacent. The minimum number of colours required for proper vertex colouring of $G$ is called the chromatic number of $G$. Then what is the chromatic number of the cycle graph on 149 vertices?

A proper vertex colouring of a graph $G$ is a colouring of the vertices in $G$ in such a way that two vertices get different colours if they are adjacent. The minimum num...

go_editor

794 views

go_editor asked Jun 8, 2016

1 votes

4 answers

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.0k views

go_editor asked May 23, 2016

24 votes

4 answers

CMI2011-A-07
Let $G=(V, E)$ be a graph. Define $\overline{G}$ to be $(V, \overline{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \overline{E}$ if and only if $(u, v) \notin E$. Then which of the following is true? $\overline{G}$ is always ... $G$ is not connected. At least one of $G$ and $\overline{G}$ connected. $G$ is not connected or $\overline{G}$ is not connected

Let $G=(V, E)$ be a graph. Define $\overline{G}$ to be $(V, \overline{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \overline{E}$ if and only if $(u, v) \notin E$...

go_editor

1.8k views

go_editor asked May 19, 2016

43 votes

4 answers

GATE CSE 2016 Set 2 | Question: 03
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

Akash Kanase

15.5k views

Akash Kanase asked Feb 12, 2016

3 votes

4 answers

subgraphs
number of subgraph for K3 is

number of subgraph for K3 is

Pooja Palod

1.4k views

Pooja Palod asked Jan 24, 2016

26 votes

4 answers

TIFR CSE 2013 | Part B | Question: 1
Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum ... $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$ None of the above

Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given di...

makhdoom ghaya

4.3k views

makhdoom ghaya asked Nov 5, 2015

3 votes

4 answers

maximum number of edges in a graph with components
A graph G have 9 vertices and two components. What is the maximum number of edges possible in this graph?

A graph G have 9 vertices and two components. What is the maximum number of edges possible in this graph?

Sankaranarayanan P.N

4.6k views

Sankaranarayanan P.N asked Jun 25, 2015

4 votes

4 answers

graph coloring
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also

What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also

Sankaranarayanan P.N

3.0k views

Sankaranarayanan P.N asked Jun 25, 2015

48 votes

4 answers

GATE CSE 2015 Set 2 | Question: 50
In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is true? A tree has no bridges A bridge cannot be part of a simple cycle Every edge of a clique with size $\geq 3$ is a bridge (A clique is any complete subgraph of a graph) A graph with bridges cannot have cycle

In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is true?A tree has no bridgesA bridge cannot be part ...

go_editor

14.6k views

go_editor asked Feb 13, 2015

1 votes

4 answers

Isomorphic graphs
Ans is a) Can anyone plz explain how G1 and G2 are isomorphic?

Ans is a) Can anyone plz explain how G1 and G2 are isomorphic?

dhingrak

1.4k views

dhingrak asked Nov 30, 2014

34 votes

4 answers

GATE IT 2008 | Question: 3
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$

What is the chromatic number of the following graph? $2$$3$$4$$5$

Ishrat Jahan

8.3k views

Ishrat Jahan asked Oct 27, 2014

26 votes

4 answers

GATE CSE 1993 | Question: 8.1
Consider a simple connected graph $G$ with $n$ vertices and $n$ edges $(n > 2)$. Then, which of the following statements are true? $G$ has no cycles The graph obtained by removing any edge from $G$ is not connected $G$ has at least one cycle The graph obtained by removing any two edges from $G$ is not connected None of the above

Consider a simple connected graph $G$ with $n$ vertices and $n$ edges $(n 2)$. Then, which of the following statements are true?$G$ has no cyclesThe graph obtained by re...

Kathleen

9.8k views

Kathleen asked Sep 29, 2014

36 votes

4 answers

GATE CSE 2014 Set 1 | Question: 52
An ordered $n-$tuple $(d_1, d_2,\ldots,d_n)$ with $d_1 \geq d_2 \geq \ldots \geq d_n$ is called graphic if there exists a simple undirected graph with $n$ vertices having degrees $d_1,d_2,\ldots,d_n$ respectively. Which one of the following $6$-tuples is NOT graphic? $(1,1,1,1,1,1)$ $(2,2,2,2,2,2)$ $(3,3,3,1,0,0)$ $(3,2,1,1,1,0)$

An ordered $n-$tuple $(d_1, d_2,\ldots,d_n)$ with $d_1 \geq d_2 \geq \ldots \geq d_n$ is called graphic if there exists a simple undirected graph with $n$ vertices havin...

go_editor

7.4k views

go_editor asked Sep 28, 2014

65 votes

4 answers

GATE CSE 2006 | Question: 71
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$

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

Rucha Shelke

17.2k views

Rucha Shelke asked Sep 26, 2014

29 votes

4 answers

GATE CSE 2012 | Question: 26
Which of the following graphs is isomorphic to

Which of the following graphs is isomorphic to

Arjun

11.1k views

Arjun asked Sep 25, 2014

Page:

« prev
1
2
3
4
5
6
7
8
9
...
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