Recent questions and answers in Graph Theory

+13 votes

3 answers

1

ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

answered 1 day ago in Graph Theory by rohith1001 (155 points) | 901 views

+4 votes

2 answers

2

MadeEasy Test Series 2018: Graph Theory - Graph Coloring
answer given is 4. Please provide a detailed solution.

answered Sep 3 in Graph Theory by Rishav_Bhatt (117 points) | 146 views

0 votes

1 answer

3

CUT-SET

answered Sep 1 in Graph Theory by Devvrat Tyagi (161 points) | 54 views

+26 votes

6 answers

4

GATE2014-2-51
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.

answered Aug 21 in Graph Theory by King Suleiman Junior (735 points) | 3.7k views

+1 vote

2 answers

5

Graph Connectivity
Consider the given statements S1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G. S2:In a simple graph G, if degree of each vertex is 3 then the graph G is connected. Which of the following is/are true?

answered Aug 5 in Graph Theory by IamDRD (25 points) | 206 views

+1 vote

2 answers

6

#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 Aug 1 in Graph Theory by Raghava45 (337 points) | 88 views

+1 vote

3 answers

7

UGCNET-June2015-II-5
Consider a Hamiltonian Graph(G) with no loops and parallel edges. Which of the following is true with respect to this graph (G)? deg (v) $\geq$ n/2 for each vertex of G $\mid E(G) \mid \geq $1/2 (n-1)(n-2)+2 edges deg(v) + deg(w) $\geq$ n fr every v and $\omega$ not connected by an edge a and b b and c a and c a, b, and c

answered Aug 1 in Graph Theory by tripu (11 points) | 1.9k views

+1 vote

1 answer

8

UGCNET-June-2019-II-69
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a real-valued function $f:V \times V \rightarrow R$: $P_1$: For all $u, v, \in V, \: f(u,v)=-f(v,u)$ $P_2$: $\underset{v \in V}{\Sigma} f(u,v)=0$ for all $u \in V$ Which one of the following is/are correct? Only $P_1$ Only $P_2$ Both $P_1$ and $P_2$ Neither $P_1$ nor $P_2$

answered Jul 29 in Graph Theory by abhinav kumar (23 points) | 45 views

+2 votes

3 answers

9

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 Jul 26 in Graph Theory by gvjha3 (11 points) | 99 views

+1 vote

1 answer

10

graph theory(basic doubt)
Q.1)How many nonisomorphic simple graph are there with 6 vertices and 4 edges??

answered Jul 24 in Graph Theory by gorya506 (173 points) | 58 views

+36 votes

7 answers

11

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 Jul 14 in Graph Theory by PRANAV M (175 points) | 3.5k views

+39 votes

3 answers

12

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 (215 points) | 4k views

0 votes

1 answer

13

planar graph
Is this a planar graph ?

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

+3 votes

1 answer

14

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 (18k points) | 100 views

+2 votes

1 answer

15

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 (18k points) | 115 views

+33 votes

7 answers

16

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 (133 points) | 4.3k views

+1 vote

1 answer

17

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 (18k points) | 292 views

0 votes

1 answer

18

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

answered Jun 21 in Graph Theory by Satbir Boss (18k points) | 241 views

+1 vote

1 answer

19

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

answered Jun 13 in Graph Theory by Gyanu Active (1.7k points) | 74 views

0 votes

1 answer

20

Zeal Test Series 2019: Graph Theory - Graph Connectivity

answered Jun 12 in Graph Theory by Gyanu Active (1.7k points) | 99 views

+2 votes

3 answers

21

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

0 votes

2 answers

22

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 (63 points) | 78 views

+1 vote

1 answer

23

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 (418k points) | 263 views

+2 votes

1 answer

24

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

answered Jun 5 in Graph Theory by Satbir Boss (18k points) | 324 views

0 votes

2 answers

25

#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) | 99 views

0 votes

1 answer

26

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

+2 votes

2 answers

27

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

0 votes

1 answer

28

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

+2 votes

3 answers

29

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.6k points) | 53 views

+1 vote

1 answer

30

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 (131 points) | 52 views

+5 votes

8 answers

31

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

+1 vote

1 answer

32

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 (18k points) | 100 views

+4 votes

0 answers

33

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 (14.3k points) | 82 views

+1 vote

2 answers

34

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 (418k points) | 132 views

+2 votes

2 answers

35

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 (418k points) | 290 views

+1 vote

0 answers

36

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.9k points) | 63 views

0 votes

0 answers

37

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 (41.4k points) | 43 views

+20 votes

5 answers

38

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 Junior (597 points) | 1.1k views

0 votes

1 answer

39

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 (14.3k points) | 78 views

+1 vote

1 answer

40

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.6k points) | 59 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