Recent questions tagged degree-of-graph / GATE Overflow for GATE CSE

89 votes

6 answers

31

GATE CSE 2006 | Question: 72
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 maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n-2}$ $2^{n-3}\times 3$ $2^{n-1}$

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

go_editor

17.8k views

go_editor asked Apr 24, 2016

3 votes

3 answers

32

Ace Test Series: Graph Theory - Degree Of Graph
How to PROVE S2 is correct?? Consider the statements $S_1$ ) In any simple graph with more than one vertex, there must exist at-least $2$ vetices of the same degree $S_2$ ) A graph with $13$ vertices, $31$ edges, $3$ vertices of degree $5$ and $7$ ... $S_2$ is false C). $S_1$ is false and $S_2$ is true D). Both $S_1$ and $S_2$ are true

How to PROVE S2 is correct??Consider the statements $S_1$ ) In any simple graph with more than one vertex, there must exist at-least $2$ vetices of the same degree $...

Tushar Shinde

1.3k views

Tushar Shinde asked Jan 13, 2016

48 votes

3 answers

33

GATE CSE 1991 | Question: 16-b
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.

Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.

Arjun

4.4k views

Arjun asked Nov 15, 2015

17 votes

3 answers

34

TIFR CSE 2012 | Part B | Question: 2
In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$? There are even number of vertices of even degree. There are odd number of vertices of even degree ... even number of vertices of odd degree. There are odd number of vertices of odd degree. All the vertices are of even degree.

In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$?There are even number of vertices...

makhdoom ghaya

3.0k views

makhdoom ghaya asked Oct 30, 2015

37 votes

6 answers

35

TIFR CSE 2010 | Part B | Question: 36
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices? Exactly seven edges leave every vertex. Exactly seven edges leave some vertex. Some vertex has at least seven edges leaving it. The number of edges coming out of vertex is odd. None of the above.

In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices?Exactly seven edges leave...

makhdoom ghaya

5.9k views

makhdoom ghaya asked Oct 10, 2015

19 votes

3 answers

36

GATE CSE 1995 | Question: 24
Prove that in finite graph, the number of vertices of odd degree is always even.

Prove that in finite graph, the number of vertices of odd degree is always even.

Kathleen

5.7k views

Kathleen asked Oct 8, 2014

36 votes

4 answers

37

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

go_editor asked Sep 28, 2014

65 votes

4 answers

38

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

Rucha Shelke asked Sep 26, 2014

25 votes

2 answers

39

GATE CSE 2013 | Question: 25
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even. P only Q only Both P and Q Neither P nor Q

Which of the following statements is/are TRUE for undirected graphs?P: Number of odd degree vertices is even.Q: Sum of degrees of all vertices is even. P only Q only Both...

Arjun

16.1k views

Arjun asked Sep 24, 2014

40 votes

7 answers

40

GATE CSE 2010 | Question: 28
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$ I and II III and IV IV only II and IV

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree...

gatecse

18.6k views

gatecse asked Sep 21, 2014

51 votes

5 answers

41

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

65 votes

9 answers

42

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

Kathleen asked Sep 17, 2014

54 votes

7 answers

43

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

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