Dark Mode

Recent questions and answers in Graph Theory

0 votes

0 answers

1

#Graphs #Self_Doubt #Connectivity
What is a biconnected componenet?Does it always include V-V’ where V’ represent the set of articulation points of a graph G?

Gate Shark asked in Graph Theory Feb 17

71 views

4 votes

2 answers

2

GATE CSE 2023 | Question: 45
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices ... $\Delta(G)$. The number of colors used is equal to the chromatic number of $G$.

Deepak Poonia answered in Graph Theory Feb 16

by Deepak Poonia

2.1k views

13 votes

4 answers

3

GATE CSE 2022 | Question: 42
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices? The diagonal entries of $A^{2}$ ... . If there is at least a $1$ in each of $A\text{'s}$ rows and columns, then the graph must be connected.

Deepak Poonia answered in Graph Theory Jan 28

by Deepak Poonia

3.4k views

1 vote

0 answers

4

TestBook graph theory question
If G is a simple planar connected graph with 5 vertices, how many edges in maximum can be there in the given graph?

Sahil_Lather asked in Graph Theory Jan 27

by Sahil_Lather

120 views

0 votes

0 answers

5

TestBook graph theory questions
Let Gn be the complete bipartite graph K13, 17 then the chromatic number of G̅n is _____ (G̅n is complement of Gn and n = 30) A 13 B 17 C n(n−1)2−13×17 D n(n−1)2−2

Sahil_Lather asked in Graph Theory Jan 27

by Sahil_Lather

86 views

0 votes

0 answers

6

TestBook Hasse Diagram question to find GLB
If [P(A); ⊆] is a lattice where A = {x, y} and P(A) is the power set then what is the sum of element in Greatest Lower Bound (GLB) set of given lattice? x + y x y 0

Sahil_Lather asked in Graph Theory Jan 27

by Sahil_Lather

48 views

42 votes

7 answers

7

GATE CSE 2006 | Question: 73
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 connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$

sameer_hack answered in Graph Theory Jan 14

6.7k views

4 votes

2 answers

8

TIFR CSE 2022 | Part B | Question: 2
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no strict superset of $M$ is a matching. How many maximal matchings does the following graph have? $1$ $2$ $3$ $4$ $5$

GNANESWARA SAI answered in Graph Theory Jan 6

by GNANESWARA SAI

311 views

0 votes

1 answer

9

Made Easy Test Series | Discrete Maths | POSET | Chain length
50 51 52 53

Souvik33 answered in Graph Theory Jan 5

152 views

1 vote

4 answers

10

CMI2013-B-03
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. Show that any finite simple graph has at least two vertices with the same degree.

GNANESWARA SAI answered in Graph Theory Jan 5

by GNANESWARA SAI

656 views

60 votes

8 answers

11

GATE IT 2006 | Question: 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 ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$

GNANESWARA SAI answered in Graph Theory Jan 5

by GNANESWARA SAI

10.5k views

3 votes

0 answers

12

graph theory
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?

Kabir5454 asked in Graph Theory Jan 2

167 views

1 vote

0 answers

13

DRDO CSE 2022 Paper 1 | Question: 9
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows. \[\left[\begin{array}{lll} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right]\]

admin asked in Graph Theory Dec 15, 2022

by admin

64 views

1 vote

0 answers

14

DRDO CSE 2022 Paper 1 | Question: 10
Given a tree $\text{T}$ and $\lambda \geq 2$ colours $\left(c_{1}, c_{2}, \ldots, c_{\lambda}\right),$ how many proper colourings of the tree $\text{T}$ are possible?

admin asked in Graph Theory Dec 15, 2022

by admin

73 views

1 vote

0 answers

15

DRDO CSE 2022 Paper 1 | Question: 11
Consider the following graph. Find closeness centrality of $\text{‘A’}$ node.

admin asked in Graph Theory Dec 15, 2022

by admin

70 views

1 vote

0 answers

16

DRDO CSE 2022 Paper 1 | Question: 13
Consider the following graph. Which nodes form the cliques of size $3?$

admin asked in Graph Theory Dec 15, 2022

by admin

62 views

27 votes

9 answers

17

GATE CSE 2015 Set 1 | Question: 54
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.

rsansiya111 answered in Graph Theory Dec 12, 2022

20.7k views

14 votes

5 answers

18

GATE CSE 2022 | Question: 20
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .

dutta18 answered in Graph Theory Dec 1, 2022

3.9k views

1 vote

1 answer

19

TIFR CSE 2022 | Part B | Question: 14
Let $G$ be a directed graph (with no self-loops or parallel edges) with $n \geq 2$ vertices and $m$ edges. Consider the $n \times m$ incidence matrix $M$ of $G$, whose rows are indexed by the vertices of $G$ and the columns by the edges of $G$ ... . Then, what is the rank of $M?$ $m-1$ $m-n+1$ $\lceil m / 2\rceil$ $n-1$ $\lceil n / 2\rceil$

Kunalbag7 answered in Graph Theory Nov 10, 2022

156 views

3 votes

1 answer

20

TIFR CSE 2022 | Part B | Question: 6
We are given a graph $G$ along with a matching $M$ and a vertex cover $C$ in it such that $|M|=|C|$. Consider the following statements: $M$ is a maximum matching in $G$. $C$ is a minimum vertex cover in $G$. $G$ is a bipartite graph. Which of ... $(1)$ and $(2)$ are correct All the three statements $(1), (2),$ and $(3)$ are correct

Deepak Poonia answered in Graph Theory Nov 9, 2022

by Deepak Poonia

361 views

0 votes

2 answers

21

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?

Purple _ rain answered in Graph Theory Oct 16, 2022

by Purple _ rain

498 views

4 votes

2 answers

22

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?

DAWID15 answered in Graph Theory Oct 13, 2022

1.7k views

2 votes

2 answers

23

Seld doubt DM
Consider a tree T with n vertices and (n – 1) edges. We define a term called cyclic cardinality of a tree (T) as the number of cycles created when any two vertices of T are joined by an edge. Given a tree with 10 vertices, what is the cyclic cardinality of this tree?

Kd55 answered in Graph Theory Oct 10, 2022

by Kd55

837 views

2 votes

4 answers

24

GATE Overflow | Mock GATE | Test 1 | Question: 34
Let $G$ be a graph of order $n$ in which every vertex has degree equal to $d$. How large must $d$ be in order to guarantee that $G$ is connected? $\frac{n}{2}$ $\lceil (n-1)/2 \rceil$ $\lfloor (n+1)/2 \rfloor$ $(n-1)/2$

Kd55 answered in Graph Theory Oct 1, 2022

by Kd55

1.4k views

1 vote

0 answers

25

TIFR CSE 2022 | Part B | Question: 12
Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sigma$ form a clique in $G$. Recall that given an undirected ... SPECIAL-COLOURING are in $\mathrm{P}$ Neither of SPECIAL-CLiQUE and SPECIAL-COLOURING is in $\mathrm{P},$ but both are decidable

admin asked in Graph Theory Sep 1, 2022

by admin

139 views

57 votes

8 answers

26

GATE CSE 2013 | Question: 26
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ ... of a planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only

Jyotish Ranjan answered in Graph Theory Aug 7, 2022

by Jyotish Ranjan

15.5k views

4 votes

2 answers

27

GO Classes Scholarship 2023 | Test | Question: 9
Consider the following graph $\text{G:}$ Let $\text{M, C, I, S, B, E}$ be the Matching number, chromatic number, independence number, Clique number, Vertex cover number, and edge cover number, respectively of $\text{G}.$ What is $\text{M+C+I+S+B+E}?$

Kabir5454 answered in Graph Theory Aug 7, 2022

410 views

3 votes

1 answer

28

GO Classes Scholarship 2023 | Test | Question: 8
In a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$, two nodes $u$ and $v$ are strongly connected if and only if they are mutually reachable i.e. there is a path from u to $v$ and a path from $v$ to $u$. ... connected components $\dots?$ can not increase can not decrease by more than $1$ can not decrease by more than $2$ may remain unchanged

GO Classes answered in Graph Theory Aug 7, 2022

386 views

3 votes

1 answer

29

GO Classes Scholarship 2023 | Test | Question: 10
For which of the following does there exist a graph satisfying the specified conditions? A tree with six vertices and six edges. A tree with three or more vertices, two vertices of degree one, and all the other vertices with degree three or ... with $10$ vertices and $8$ edges. A disconnected graph with $12$ vertices and $11$ edges and no cycle.

GO Classes answered in Graph Theory Aug 7, 2022

263 views

4 votes

1 answer

30

GO Classes Scholarship 2023 | Test | Question: 12
How many non-isomorphic simple undirected graphs are there, each with four vertices and without a cycle?

GO Classes answered in Graph Theory Aug 7, 2022

309 views

66 votes

12 answers

31

GATE CSE 1994 | Question: 1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$

Cs_Gate_22 answered in Graph Theory Aug 4, 2022

28.7k views

58 votes

4 answers

32

GATE CSE 2003 | Question: 8, ISRO2009-53
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$

Abhrajyoti00 answered in Graph Theory Jul 23, 2022

by Abhrajyoti00

12.3k views

0 votes

1 answer

33

Self Doubt - Planarity of Complete Bipartite Graph
How to determine for which m, n the complete bipartite graph $Km,n$ is planar? I am getting two answers from two sources:- A complete bipartite graph $Kmn$ is planar if and only if m<3 or n>3. Source: https://www.javatpoint.com/ ... m ≤ 2 or n ≤ 2. Source: http://www.matthewkahle.org/download/file/fid/573 Need a proper proof of the solution.

Abhrajyoti00 asked in Graph Theory Jul 21, 2022

by Abhrajyoti00

253 views

0 votes

1 answer

34

Degree sequence of graph
Someone please solve it.

Overflow04 asked in Graph Theory Jun 30, 2022

217 views

0 votes

1 answer

35

Doubt:
Let “m” be the number of edges, “n” the number of vertices and “k” the number of connected components of a graph G. Prove that: $\left ( n-k \right )\leq m\leq \frac{\left ( n-k \right )\left ( n-k+1 \right )}{2}$ Why least number of edges are $\left ( n-k \right )$ and Why most number of edges are $\frac{\left ( n-k \right )\left ( n-k+1 \right )}{2}$ ? What is the idea behind this prove?

RKM asked in Graph Theory Jun 28, 2022

by RKM

221 views

0 votes

0 answers

36

Introduction to Graph Theory Exercises
This is the problem snapshot

AngshukN asked in Graph Theory May 22, 2022

243 views

0 votes

1 answer

37

What is the number of faces in a connected plane graph having 23 vertices, 30 edges?
What is the number of faces in a connected plane graph having 23 vertices, 30 edges?

R S BAGDA asked in Graph Theory Apr 27, 2022

154 views

12 votes

2 answers

38

GATE CSE 2022 | Question: 27
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of $\textit{A}^{3}$ $\textit{A}^{3}$ divided by $2$ $\textit{A}^{3}$ divided by $3$ $\textit{A}^{3}$ divided by $6$

Arjun asked in Graph Theory Feb 15, 2022

by Arjun

3.4k views

11 votes

2 answers

39

GATE CSE 2022 | Question: 40
The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are $\text{TRUE}?$ The chromatic number of the graph is $3.$ The graph has a Hamiltonian path. The following graph is isomorphic to the Peterson ... $3.$ (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

Arjun asked in Graph Theory Feb 15, 2022

by Arjun

3.7k views

1 vote

0 answers

40

Made Easy Full length Test
Options Given were---- ADC ABC Both the above None of these According to me the answer should be {A,B,C,D} as this is the largest set and every node is capable to reach every other node.. but the answer given was option C so can anyone plz tell me whats the correct answer?

Sagar475 asked in Graph Theory Jan 18, 2022

226 views

To see more, click for all the questions in this category.

Recent questions and answers in Graph Theory