Recent questions and answers in Graph Theory

+33 votes

5 answers

1

GATE2006-IT-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 flipping a single ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$

answered 2 days ago in Graph Theory by Kuljeet Shan Junior (657 points) | 2.5k views

0 votes

0 answers

2

Graph Decomposition
What is Graph Decomposition & is it in the syllabus? If it is then please can anyone share some online resources for it. Thank you.

asked 5 days ago in Graph Theory by noxevolution (73 points) | 13 views

+1 vote

1 answer

3

Zeal Test Series 2019: Graph Theory - Graph Matching

answered Mar 7 in Graph Theory by abhishekmehta4u Boss (29k points) | 55 views

0 votes

0 answers

4

Narsingh deo
What is meant by edge disjoint hamiltonian circuits in a graph

asked Mar 5 in Graph Theory by Winner (123 points) | 35 views

+1 vote

1 answer

5

Strongly Connected, Unilaterally connected and weakly Connected
Hi Guys, Is there any quick way of verifying Graph is Strongly Connected, Unilaterally connected and weakly Connected ? For Example - If 1 dead point then graph is Unilaterally Connected and If 2 dead points then graph is Weakly Connected.

answered Feb 22 in Graph Theory by saurav raghaw Active (1.3k points) | 314 views

+2 votes

1 answer

6

GATE - 2014 - 1- 51 modified
Consider an directed graph G where self-loops are not allowed. The vertex set of G is {(i,j)∣1≤i≤12,1≤j≤12}There is an edge from(a,b) to (c,d) if |a−c|≤1 and |b−d|≤1. The number of edges in this graph is______

answered Feb 18 in Graph Theory by Priyadrasta Raut (373 points) | 127 views

0 votes

0 answers

7

JEST 2019
A directed graph with n vertices, in which each vertex has exactly 3 outgoing edges. Which one is true? A) All the vertices have indegree = 3 . B) Some vertices will have indegree exactly 3. C)Some vertices have indegree atleast 3. D) Some of the vertices have indegree atmost 3

asked Feb 18 in Graph Theory by Sayan Bose Loyal (5.9k points) | 51 views

0 votes

0 answers

8

JEST 2019 Descriptive Q2 (8 Marks)
Given a sequence $a_1$, $a_2$ , $a_3$ ... $a_n$ of any different positive integers, exhibit an arrangement of integers between 1 and $n^2$ which has no increasing or decreasing subsequence of length n+1.

asked Feb 17 in Graph Theory by dan31 Junior (689 points) | 56 views

0 votes

0 answers

9

JEST 2019 Descriptive Q1 (8 Marks)
Suppose that G contains a cycle C, and a path of length at least k between some two vertices of C. Show that G contains a cycle of length at least √k.

asked Feb 17 in Graph Theory by dan31 Junior (689 points) | 35 views

+12 votes

3 answers

10

CMI2013-A-06
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.Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex of ... degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$

answered Feb 15 in Graph Theory by Satbir Loyal (5.3k points) | 580 views

0 votes

4 answers

11

GATE2019-12
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$

answered Feb 14 in Graph Theory by OO7 Junior (579 points) | 2.5k views

+21 votes

8 answers

12

GATE2017-2-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 _________ .

answered Feb 8 in Graph Theory by Suneel Padala Junior (737 points) | 4.2k views

+1 vote

1 answer

13

GATE2019-38
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II

answered Feb 7 in Graph Theory by Digvijay Pandey Veteran (59.5k points) | 2k views

0 votes

1 answer

14

GATE 2019 8
Q.8 Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to 1. (n-1)!/2 2. 1 3.(n-1)! 4. n!

answered Feb 7 in Graph Theory by Sahil Arora 2 (15 points) | 290 views

0 votes

2 answers

15

GATE2019
What is the total number of different Hamiltonian cycles for the complete graph of n vertices?

answered Feb 3 in Graph Theory by Sumit Rana 1 Junior (793 points) | 709 views

0 votes

0 answers

16

Abelian group
A quick question Is every multiplication modulo function a Abelian group....Or is it the case that the function should have prime number as modulo

asked Feb 2 in Graph Theory by Nandkishor3939 Active (1.2k points) | 35 views

0 votes

4 answers

17

GateForum Test Series: Graph Theory - Graph Coloring
The Chromatic Number of Cycle Graph with 7 vertices _____

answered Feb 1 in Graph Theory by Sai Shravan (149 points) | 315 views

0 votes

0 answers

18

GeeksforGeeks
Let G be a graph with no isolated vertices, and let M be a maximum matching of G. For each vertex v not saturated by M, choose an edge incident to v. Let T be the set of all the chosen edges, and let L = M ∪ T. Which of the following option is TRUE? A L is always ... G. B L is always a minimum edge cover of G. C Both (A) and (B) D Neither (A) nor (B) Can anyone pls help solving this?

asked Jan 30 in Graph Theory by Ashish Goyal (343 points) | 103 views

0 votes

0 answers

19

Madeeasy
A graph G is called self complementary iff G is isomorphic to its complement. Let X be a self complementary graph. Which of the following is a viable possibility with regards to the connectivity of X and X', where X' denotes the complement of X, ... answer such questions. So the conclusion is "Every sell complementary graph is cormected". So option (d) is the correct answer.

asked Jan 29 in Graph Theory by mehul vaidya Active (3.2k points) | 25 views

0 votes

0 answers

20

selfdoubt-ME-testseries
we define a new measure ,called GoldIndex(G,C).it takes two arguments as input namely a graph G and set of colors C respectively . the subroutine outputs an integer denoting the number of ways assigning colors to vertices in G such that at least two vertices ... 't know where m i going wrong ,please help me- i know their solution is correct but i want to verify my approach- [closed]

asked Jan 29 in Graph Theory by Prateek Raghuvanshi Loyal (9.7k points) | 64 views

0 votes

1 answer

21

#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.

answered Jan 29 in Graph Theory by prashant jha 1 Active (4.7k points) | 65 views

0 votes

0 answers

22

max weighted MST possible
Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have. Then the value of x will be_____ the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out in understanding the procedure

asked Jan 26 in Graph Theory by Nandkishor3939 Active (1.2k points) | 74 views

0 votes

0 answers

23

Made Easy Practice Book
The number of labelled subgraph possible for the graph given below are ________.

asked Jan 25 in Graph Theory by Shankar Kakde (369 points) | 34 views

0 votes

1 answer

24

ACE TEST SERIES QUESTION ON Graph Theory

answered Jan 25 in Graph Theory by soubhik baral (229 points) | 39 views

0 votes

0 answers

25

Counting

asked Jan 25 in Graph Theory by screddy1313 (401 points) | 31 views

0 votes

1 answer

26

ACE Test series question on Chromatic number

answered Jan 25 in Graph Theory by Sai Shravan (149 points) | 46 views

0 votes

2 answers

27

Applied Course 2019 Mock1-36
Naveen invited seven of his friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the same person more than once. After the party, Naveen asked each of his seven friends ... distinct positive integers. Given that his friends were truthful, how many hands did Naveen shake? $4$ $5$ $6$ $7$

answered Jan 25 in Graph Theory by Utkarsh Joshi Loyal (7.2k points) | 85 views

0 votes

0 answers

28

SelfDoubt
A graph with each vertex has even degree contain Hamiltonian Cycle. True/False plz explain how to ensure Hamiltonian Cycle.

asked Jan 25 in Graph Theory by Abhisek Tiwari 4 Active (4.2k points) | 47 views

0 votes

1 answer

29

Virtual Gate
A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?

answered Jan 24 in Graph Theory by Sushant Devkar (177 points) | 67 views

+1 vote

2 answers

30

GATEBOOK-2019 Mock Test1-40
The number of graphs possible with $5$ vertices and $3$ edges is ____ $10$ $15$ $5$ $120$

answered Jan 23 in Graph Theory by gmrishikumar Active (1.7k points) | 255 views

+1 vote

1 answer

31

GATEBOOK-2019 Mock Test1-39
Consider the collection of all un directed graphs with $10$ nodes and $6$ edges. Let M and m, respectively, be the maximum and minimum number of connected components in any graph in the collection. If a graph has no self loops and there is at most one edge between any pair of nodes, which of the ... $M = 10, \: m = 1$ $M = 7, \: m = 4$ $M = 6, \: m = 4$

answered Jan 23 in Graph Theory by Ashwani Kumar 2 Boss (14.9k points) | 130 views

0 votes

2 answers

32

MadeEasy Test Series: Graph Theory
How to solve such problems?

answered Jan 22 in Graph Theory by royal shubham Junior (557 points) | 107 views

0 votes

2 answers

33

Suppose a connected graph has 15 labeled nodes
Suppose a connected graph has 15 labeled nodes, given that it has an eularian circuit, what is the minimum number of distinct circuits which it must have? [Note : the circuit a->b->c->a is not same as b->c->a->b]

answered Jan 21 in Graph Theory by abhigpt95 (97 points) | 206 views

0 votes

0 answers

34

SelfDoubt
Checking for Euler Path i.A graph has Euler path if exactly two vertices is of odd degree. if a graph have euler circuit=>all vertices even degree=>euler circuit which already cover euler path. am i correct? i is necessary and sufficient condition? So for ... check either 1.Euler Circuit or 2.Exactly two odd degree then it will have euler path but not euler circuit. is it correct? [closed]

asked Jan 20 in Graph Theory by Abhisek Tiwari 4 Active (4.2k points) | 31 views

0 votes

1 answer

35

MadeEasy Test Series: Discrete Mathematics - Graph Thoery
The number of labelled subgraphs possible for the graph given below.

answered Jan 20 in Graph Theory by balchandar reddy san Active (2.7k points) | 227 views

0 votes

0 answers

36

Ace Test Series: Graph Theory - Cut Edges
If G is a connected simple graph with 10 vertices in which degree of every vertex is 2 then number of cut edges in G is ?

asked Jan 19 in Graph Theory by Na462 Loyal (8.7k points) | 62 views

0 votes

0 answers

37

made easy adv mock
A graph G is self complementary iff G is isomorphoc to its complement.Let X be a self complementary graph.Which of the following is a viable possibility with regards to connectivity of X and X' ,where X' denotes the complement of X? a)both X and X' are ... X' is disconnected c)X' is connected and X' is disconnected d)both X and X' are connected ans is (d) pls explain

asked Jan 18 in Graph Theory by Gate Fever Active (4.7k points) | 34 views

0 votes

1 answer

38

ME test series question on graph theory

answered Jan 18 in Graph Theory by Priyadrasta Raut (373 points) | 58 views

+51 votes

7 answers

39

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 Jan 17 in Graph Theory by Apoorva Jain (455 points) | 6.6k views

+1 vote

2 answers

40

MadeEasy Subject Test 2019: Graph Thoery - Graph Coloring
The number of vertices,edges and colors required for proper coloring in Tripartite graph K<3,2,5> will be : 10 , 31 , 3 10 , 30 , 3 10 , 30 , 2 None

answered Jan 17 in Graph Theory by muthu kumar Active (1.5k points) | 67 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