Recent questions and answers in Graph Theory

0 votes

1 answer

1

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

answered 1 day ago in Graph Theory by Shaik Masthan Boss (25.9k points) | 6 views

0 votes

1 answer

2

DSA-Test 3-Question 10
For which of the following scenarios does there exist a simple graph G = (V, E) satisfying the specified conditions? (A) It has 3 components 20 vertices and 16 edges. (B) It has 10 vertices, 38 edges, and more than one component. (C) It has 7 vertices, 10 edges, and more than two components. (D) It is connected and has 10 edges 5 vertices and fewer than 6 cycles.

answered 1 day ago in Graph Theory by Shaik Masthan Boss (25.9k points) | 7 views

0 votes

0 answers

3

DSA-Test 3-Question 12
Let T = (V, E) be a tree and let d(v) be the degree of a vertex. Consider following statements: (i) P v∈V (2 − d(v)) = 2 (ii) If T has a vertex of degree m ≥ 2, then it has at least m vertices of degree 1. (iii) P v∈V (k − d(v)) = k, for k ≥ 2 | k ∈ ... of the above statements is/are ture: (A) (i) only (B) (i), (ii) only (C) (ii) and (iii) only (D) (i), (ii) and (iii) only

asked 1 day ago in Graph Theory by Sandy Sharma Junior (837 points) | 3 views

0 votes

1 answer

4

Graph Theory
Please help with the following:- 1)How to determine if a graph is bipartite or not? 2)What is meant by ordered pair in case of a directed graph and unordered pair in case of an undirected graph?

answered 1 day ago in Graph Theory by Shaik Masthan Boss (25.9k points) | 12 views

0 votes

1 answer

5

DSA-Test 3-Question 3
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with 10 vertices, where cardinalities of those five sets are given as {2,3,2,1,2}, is: (A) 16 (B) 20 (C) 26 (D) 39

answered 1 day ago in Graph Theory by Shaik Masthan Boss (25.9k points) | 9 views

0 votes

0 answers

6

DSA-Test 3-Question 5
Consider following statements about tripartite graph, i.e. TPG, which contains three subsets of vertices of graph as A,B and C: (i) Minimum number of edges in a cycle in a TPG which passes through all three subsets of vertices is 6. (ii) A complete TPG can be colored with atmost 3 ... are true: (A) (i) only (B) (iii) only (C) (ii) and (iii) only (D) (i) and (ii) only

asked 1 day ago in Graph Theory by Sandy Sharma Junior (837 points) | 2 views

0 votes

1 answer

7

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

answered 5 days ago in Graph Theory by Magma Active (2.1k points) | 25 views

0 votes

0 answers

8

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

asked 5 days ago in Graph Theory by venkatesh456 (9 points) | 14 views

0 votes

0 answers

9

nielit 2017
If G is an undirected planar graph on n vertices with e edges then A) e<=n B) e<=2n C) e<=3n D) None of the option plz explain it with solutions

asked Sep 10 in Graph Theory by RiteshSingh (249 points) | 34 views

0 votes

1 answer

10

UGCNET-june2008-ii-4
The set of positive integers under the operation of ordinary multiplication is: (A) not a monoid (B) not a group (C) a group (D) an Abelian group

answered Sep 10 in Graph Theory by RiteshSingh (249 points) | 176 views

0 votes

2 answers

11

ME test series.
How 14? I am not able to understand. Why not 30.

answered Sep 6 in Graph Theory by sakharam Active (2k points) | 62 views

0 votes

0 answers

12

SELF DOUBT
https://gateoverflow.in/931/gate2003-40 IN THE SOLUTION AT LAST 3 STATEMENTS 0≤−6. which is definitely inconsistent. Hence, answer = option (D) WE PUT 6 HERE THEN IF WE DONT HAVE VALUES MEANS FILL IN THE BLANKS THEN.............. IS THERE ANY METHOD TO SOLVE THIS OR ANYTHING ??????

asked Sep 2 in Graph Theory by Deepanshu Active (1.7k points) | 16 views

0 votes

2 answers

13

kenneth H rosen 7th ed. Ex- 10.3 q-28
What is the sum of the entries in a row of the adjacency matrix for an undirected graph? For a directed graph?

answered Sep 2 in Graph Theory by abhishek kumar 34 (39 points) | 307 views

0 votes

1 answer

14

Iso-morphic || Non-Isomorphic Graphs
The Number of Non-Isomorphic simple graphs upto 5 Nodes is _______

answered Sep 2 in Graph Theory by RashmiNitwane (11 points) | 268 views

0 votes

0 answers

15

Doubt
What is converse of a graph?

asked Sep 1 in Graph Theory by aditi19 Junior (647 points) | 11 views

0 votes

0 answers

16

NIELIT2017 STA-set-c-119
The function $f(x)=\frac{x^2 -1}{x-1}$ at $x=1$ is: (A) Continuous and Differentiable (B) Continuous but not Differentiable (C) Differentiable but not Continuous (D) Neither Continuous nor Differentiable

asked Aug 31 in Graph Theory by habedo007 Active (2k points) | 15 views

+19 votes

6 answers

17

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

answered Aug 27 in Graph Theory by shivamshukla (29 points) | 3.7k views

+22 votes

6 answers

18

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

answered Aug 26 in Graph Theory by shivamshukla (29 points) | 2.4k views

+1 vote

0 answers

19

Kenneth Rosen Discrete Mathematics
DIRAC’S THEOREM: If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit. The below graph does not follow the above rule but still have a Hamilton circuit.

asked Aug 25 in Graph Theory by CJ147 (43 points) | 23 views

0 votes

1 answer

20

Graphs, kenneth rosen
How many non-isomorphic simple graphs are there with five vertices and three edges?

answered Aug 25 in Graph Theory by Mk Utkarsh Boss (16.6k points) | 26 views

+1 vote

1 answer

21

Number of Eulerian Graphs
Find the number of connected Eulerian graphs with 6 unlabelled vertices. Draw each of them. Note: I'm looking for a fast procedure don't comment just the numerical answer.

answered Aug 24 in Graph Theory by arvin Loyal (7.7k points) | 52 views

+14 votes

3 answers

22

GATE2005-35
How many distinct binary search trees can be created out of $4$ distinct keys? $5$ $14$ $24$ $42$

answered Aug 24 in Graph Theory by Mk Utkarsh Boss (16.6k points) | 1.5k views

+30 votes

6 answers

23

GATE2003-36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$

answered Aug 23 in Graph Theory by Vijay Dulam (85 points) | 3.5k views

+1 vote

2 answers

24

Doubt
For a complete graph with 10 vertices, The number of spanning trees is at least_____?

answered Aug 23 in Graph Theory by arvin Loyal (7.7k points) | 34 views

0 votes

2 answers

25

Proper edge coloring
What is the minimal number K such that there exists a proper edge coloring of the complete graph on 8 vertices with K colors? A) 28 B) 8 C) 7 D) 15

answered Aug 20 in Graph Theory by Rishav Kumar Singh Active (4.2k points) | 70 views

0 votes

1 answer

26

Graph theory
In tree for every pair of vertices u!=v in G their is exactly 1 path from u to v .Please help me to prove this

answered Aug 17 in Graph Theory by goxul Active (2.3k points) | 27 views

+11 votes

3 answers

27

GATE2008-23
Which of the following statements is true for every planar graph on $n$ vertices? The graph is connected The graph is Eulerian The graph has a vertex-cover of size at most $\frac{3n}{4}$ The graph has an independent set of size at least $\frac{n}{3}$

answered Aug 16 in Graph Theory by Pratik Gawali (169 points) | 1.7k views

0 votes

1 answer

28

me test
A simple graph with n vertices is constructed by randomly and independently placing an edge between every two vertices with probability p. What is the expected no. of nodes with degree 2?

answered Aug 14 in Graph Theory by MansiS (93 points) | 46 views

+1 vote

2 answers

29

Graph theory Modified
What is the maximum integer value m such that every simple connected graph with r vertices and r+2 edges contains at least m different spanning trees ? 1)1 2)4 3)8 4)m

answered Aug 14 in Graph Theory by Surajit13 (11 points) | 141 views

+3 votes

2 answers

30

How many maximum cycles possible in any Complete graph? (Unlabelled nodes)

answered Aug 14 in Graph Theory by K_Nishant (75 points) | 238 views

+4 votes

2 answers

31

Number of Hamiltonian cycles in a complete graph

answered Aug 13 in Graph Theory by K_Nishant (75 points) | 361 views

+1 vote

4 answers

32

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

answered Aug 9 in Graph Theory by JPranavc (281 points) | 337 views

+43 votes

5 answers

33

GATE2014-1-51
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.

answered Aug 9 in Graph Theory by sutanay3 Active (2.6k points) | 4.9k views

+3 votes

2 answers

34

Non-isomorphic graphs
How many non-isomorphic simple graph are there with N vertices, where N = 4 ?

answered Aug 9 in Graph Theory by K_Nishant (75 points) | 1.9k views

0 votes

1 answer

35

Ace material
If a graph with 10 vertices having each vertex having degree >=5 find graph connected or disconnected

answered Aug 8 in Graph Theory by sourav. Boss (16.1k points) | 18 views

0 votes

1 answer

36

ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.

answered Aug 8 in Graph Theory by gparamesh.1997 (17 points) | 84 views

0 votes

0 answers

37

Graph Theory
[closed]

asked Aug 6 in Graph Theory by BharathiCH (195 points) | 15 views

0 votes

0 answers

38

Show that T is a maximum spanning tree for G

asked Jul 24 in Graph Theory by abram19000 (7 points) | 28 views

+1 vote

1 answer

39

ACE Bits And Bytes
Number of perfect matching in Wn (n>=4 and n is even) _________.

answered Jul 24 in Graph Theory by Shaik Masthan Boss (25.9k points) | 40 views

0 votes

1 answer

40

Graphs

answered Jul 20 in Graph Theory by Shaik Masthan Boss (25.9k points) | 46 views

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

Recent questions and answers in Graph Theory

Recent Posts

Recent Blog Comments