Search results for graph-theory / GATE Overflow for GATE CSE

65 votes

9 answers

21

GATE CSE 2003 | Question: 40
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$

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

Kathleen

15.6k views

Kathleen asked Sep 17, 2014

59 votes

8 answers

22

GATE CSE 2013 | Question: 26
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 ... 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

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

Arjun

19.0k views

Arjun asked Sep 24, 2014

65 votes

5 answers

23

GATE CSE 2003 | Question: 8, ISRO2009-53
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{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$

Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must neces...

Kathleen

15.4k views

Kathleen asked Sep 16, 2014

53 votes

6 answers

24

GATE CSE 2001 | Question: 2.15
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} $

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^\f...

Kathleen

14.1k views

Kathleen asked Sep 14, 2014

14 votes

3 answers

25

GATE CSE 2022 | Question: 27
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of $\textit{A}^{3}$ $\textit{A}^{3}$ divided by $2$ $\textit{A}^{3}$ divided by $3$ $\textit{A}^{3}$ divided by $6$

Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the g...

Arjun

7.5k views

Arjun asked Feb 15, 2022

64 votes

9 answers

26

GATE IT 2006 | Question: 25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$

Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if ...

Ishrat Jahan

13.2k views

Ishrat Jahan asked Oct 31, 2014

7 votes

3 answers

27

GATE CSE 2023 | Question: 45
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices ... $\Delta(G)$. The number of colors used is equal to the chromatic number of $G$.

Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=...

admin

8.3k views

admin asked Feb 15, 2023

44 votes

9 answers

28

GATE CSE 2017 Set 2 | Question: 23
$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 _________ .

$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 _________ .

Madhav

17.5k views

Madhav asked Feb 14, 2017

39 votes

8 answers

29

GATE CSE 2002 | Question: 1.25, ISRO2008-30, ISRO2016-6
The maximum number of edges in a $n$-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$

The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$

Kathleen

18.7k views

Kathleen asked Sep 15, 2014

49 votes

11 answers

30

GATE CSE 2009 | Question: 2
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$

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$

gatecse

13.2k views

gatecse asked Sep 15, 2014

37 votes

7 answers

31

GATE CSE 2004 | Question: 77
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is $2$ $3$ $4$ $5$

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is$2$$3$$4$$5$

Kathleen

12.7k views

Kathleen asked Sep 18, 2014

51 votes

4 answers

32

GATE CSE 1991 | Question: 01,xv
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.

The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.

Kathleen

11.6k views

Kathleen asked Sep 12, 2014

19 votes

5 answers

33

GATE CSE 2022 | Question: 20
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .

Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .

Arjun

8.8k views

Arjun asked Feb 15, 2022

54 votes

7 answers

34

GATE CSE 2009 | Question: 3
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.

Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices ...

gatecse

11.4k views

gatecse asked Sep 15, 2014

16 votes

3 answers

35

number of perfect matching in complete graph
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?

Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?

dhingrak

10.8k views

dhingrak asked Dec 2, 2014

16 votes

4 answers

36

GATE CSE 2022 | Question: 42
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices? The diagonal entries of $A^{2}$ ... . If there is at least a $1$ in each of $A\text{'s}$ rows and columns, then the graph must be connected.

Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?The diagonal entries of $A^{2}$ are the degrees of t...

Arjun

7.4k views

Arjun asked Feb 15, 2022

51 votes

5 answers

37

GATE CSE 2010 | Question: 1
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$

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

gatecse

11.5k views

gatecse asked Sep 21, 2014

2 votes

2 answers

38

GATE CSE 2024 | Set 2 | Question: 7
Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following statements is always TRUE? $\text{G}$ is a cycle $\text{G}$ is a perfect matching $\text{G}$ is a complete graph There is no such graph $\text{G}$

Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following statements i...

Arjun

2.8k views

Arjun asked Feb 16

46 votes

6 answers

39

GATE CSE 2002 | Question: 1.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$

The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is$2$$3$$4$$n-2 \lef...

Kathleen

11.2k views

Kathleen asked Sep 15, 2014

1 votes

3 answers

40

GATE CSE 2024 | Set 2 | Question: 50
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

Arjun

1.9k views

Arjun asked Feb 16

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