Recent questions and answers in Graph Theory

+35 votes

7 answers

1

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

answered 3 days ago in Graph Theory by PRANAV M (129 points) | 3.4k views

+38 votes

3 answers

2

GATE2004-79
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k\\$ $^{\left(\frac{n^2-n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$

answered Jul 5 in Graph Theory by pritishc (81 points) | 3.9k views

0 votes

1 answer

3

planar graph
Is this a planar graph ?

answered Jul 4 in Graph Theory by Peyush (11 points) | 88 views

+1 vote

1 answer

4

UGCNET-June-2019-II-5
For which values of $m$ and $n$ does the complete bipartite graph $k_{m,n}$ have a Hamiltonian circuit ? $m\neq n,\ \ m,n \geq 2$ $m\neq n,\ \ m,n \geq 3$ $m=n,\ \ m,n \geq 2$ $m= n,\ \ m,n \geq 3$

answered Jul 3 in Graph Theory by Satbir Boss (15.3k points) | 43 views

+1 vote

1 answer

5

UGCNET-June-2019-II-4
Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph? $6$ $8$ $12$ $20$

answered Jul 3 in Graph Theory by Satbir Boss (15.3k points) | 63 views

0 votes

0 answers

6

UGCNET-June-2019-II-69

asked Jul 2 in Graph Theory by Arjun Veteran (413k points) | 14 views

+32 votes

7 answers

7

GATE2014-3-51
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $n-k$ $n-k+1$

answered Jun 25 in Graph Theory by ankitrazzagmail.com (91 points) | 4.2k views

+1 vote

1 answer

8

Graph Coloring
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ? There is a condition that adjacent vertices should not be of the same color I am getting $1680$. Is it correct?

answered Jun 21 in Graph Theory by Satbir Boss (15.3k points) | 285 views

0 votes

1 answer

9

Planar Graph
Can minimum degree of a planar graph be $5$? Give some example

answered Jun 21 in Graph Theory by Satbir Boss (15.3k points) | 238 views

+1 vote

1 answer

10

Doubt
How many distinct unlabeled graphs are there with 4 vertices and 3 edges?

answered Jun 13 in Graph Theory by Gyanu Active (1.6k points) | 72 views

0 votes

1 answer

11

Zeal Test Series 2019: Graph Theory - Graph Connectivity

answered Jun 12 in Graph Theory by Gyanu Active (1.6k points) | 88 views

+2 votes

3 answers

12

Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? Vertex $n$ has degree $1$ Graph is connected There is a path from vertex $1$ to vertex $n$ Spanning tree will include edge connecting vertex $1$ and vertex $n$

answered Jun 12 in Graph Theory by Sainath Mandavilli (23 points) | 115 views

0 votes

2 answers

13

ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree-1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree-4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.

answered Jun 12 in Graph Theory by Akanksha Agrawal (37 points) | 70 views

+1 vote

1 answer

14

TIFR2019-B-12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every ... $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle

answered Jun 8 in Graph Theory by Arjun Veteran (413k points) | 252 views

+2 votes

1 answer

15

GATE1987-9d
Specify an adjacency-lists representation of the undirected graph given above.

answered Jun 5 in Graph Theory by Satbir Boss (15.3k points) | 304 views

0 votes

2 answers

16

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

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 95 views

+1 vote

1 answer

17

#ACE_ACADEMY_DISCRETE_MATHS_BOOKLET.
Which of the following is not true? (a) Number of edge-disjoint Hamiltonian cycles in $K_7$ is $3$ (b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in ... simple graph with $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$ Please help me understand all the options.

answered Jun 4 in Graph Theory by chandan2teja (127 points) | 41 views

0 votes

1 answer

18

self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 52 views

+2 votes

2 answers

19

GateForum Question Bank :Graph Theory
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 108 views

0 votes

1 answer

20

self-doubt
A graph with alternating edges and vertices is called a walk (we can repeat the number of vertices and edges any number of times) . A walk in which no edges are repeated is called a trial. A trial in which no vertices are repeated is called a path. A trial in which only the starting and ending vertices are repeated is called a circuit. Are the definitions correct??

answered Jun 4 in Graph Theory by rballiwal Active (1.2k points) | 22 views

+1 vote

3 answers

21

Ace academy booklet #graph theory
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Euler circuit exists $\Leftrightarrow$ $n$ is odd. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Euler circuit exists ... Euler circuit exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Euler circuit exits $\Leftrightarrow$ $n$ is even.

answered Jun 4 in Graph Theory by abhishekmehta4u Boss (34.2k points) | 45 views

+1 vote

1 answer

22

ACE ACADEMY BOOKLET
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Hamiltonian cycle exists for all n. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Hamiltonian cycle exists $\Leftrightarrow$ ... Hamiltonian cycle exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Hamiltonian cycle exits $\Leftrightarrow$ $n$ is even.

answered Jun 4 in Graph Theory by chandan2teja (127 points) | 43 views

+4 votes

8 answers

23

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 Jun 3 in Graph Theory by akshay96 (11 points) | 2.9k views

+2 votes

2 answers

24

ACE ACADEMY BOOKLET QUESTION
Let $G$ $=$ $(V, E)$ be a simple non-empty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two non-empty and non-overlapping subsets $S$ and $T$. Which of the following is true? There are at least two edges that ... $S$ and one end point in $T$ There are exactly one edge that have one end point in $S$ and one end point in $T$

answered May 28 in Graph Theory by Deepakk Poonia (Dee) Boss (25k points) | 84 views

+1 vote

1 answer

25

Made easy Test Series:Graph Theory+Automata
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________

answered May 23 in Graph Theory by Satbir Boss (15.3k points) | 80 views

+3 votes

0 answers

26

IISc CSA - Research Interview Question
Prove that the rank of the Adjacency Matrix which is associated with a $k-$ regular graph is $k.$

asked May 22 in Graph Theory by ankitgupta.1729 Boss (13.7k points) | 77 views

+1 vote

2 answers

27

CMI2011-B-01b
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. ... preferred roads differing in at least one road? Substantiate your answers by either proving the assertion or providing a counterexample.

answered May 19 in Graph Theory by Arjun Veteran (413k points) | 131 views

+2 votes

2 answers

28

GATE1989-4-vii
Provide short answers to the following questions: In the graph shown above, the depth-first spanning tree edges are marked with a 'T'. Identify the forward, backward and cross edges.

answered May 18 in Graph Theory by Arjun Veteran (413k points) | 276 views

0 votes

0 answers

29

Difference between DAG and Multi-stage graph
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?

asked Apr 28 in Graph Theory by gmrishikumar Active (1.8k points) | 54 views

0 votes

0 answers

30

ISI2017-PCB-B-1(b)
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.

asked Apr 8 in Graph Theory by akash.dinkar12 Boss (40.9k points) | 41 views

+18 votes

5 answers

31

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

answered Mar 29 in Graph Theory by Debargha Bhattacharj (453 points) | 1k views

0 votes

1 answer

32

Allen Career Institute: Spanning tree
Let $G$ be a simple undirected complete and weighted graph with vertex set $V = {0, 1, 2, . 99.}$ Weight of the edge $(u, v)$ is $\left | u-v \right |$ where $0\leq u, v\leq 99$ and $u\neq v$. Weight ... tree is______________ Doubt:Here asking for maximum weight spanning tree. So, there weight will be $0$ to every node. Isnot it? but answer given 7351.

answered Mar 29 in Graph Theory by ankitgupta.1729 Boss (13.7k points) | 75 views

+1 vote

1 answer

33

Allen Career Institute:Graph Theory
If G be connected planar graph with 12 vertices of deg 4 each. In how many regions can this planar graph be partitioned?

answered Mar 28 in Graph Theory by abhishekmehta4u Boss (34.2k points) | 59 views

+33 votes

5 answers

34

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 Mar 20 in Graph Theory by Kuljeet Shan Active (1.5k points) | 2.7k views

0 votes

0 answers

35

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 Mar 17 in Graph Theory by noxevolution (93 points) | 35 views

+1 vote

1 answer

36

Zeal Test Series 2019: Graph Theory - Graph Matching

answered Mar 7 in Graph Theory by abhishekmehta4u Boss (34.2k points) | 85 views

0 votes

0 answers

37

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

asked Mar 5 in Graph Theory by Winner (249 points) | 65 views

+1 vote

1 answer

38

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) | 496 views

+2 votes

1 answer

39

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) | 138 views

+1 vote

0 answers

40

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 (7k points) | 87 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