Register
Webpage for Graph Theory:

Recent questions tagged graph-theory

243
views
1 answers
0 votes
isi mtech cse 2024 admission test
For any undirected connected graph \( G \), let \( \chi(G) \) be the minimum number of colours needed to colour all the vertices of \( G \) in such a way that no two adjacent ... i}, v_{i+1}\right) \) is an edge for \( 1 \leq i \leq k \)
User Avatar
105
views
0 answers
0 votes
ISI PCB 2023 Q3
User Avatar
240
views
1 answers
0 votes
ISI kolkata MTech CS 2019
Let $K_n$ denote the complete graph on $n$ vertices, with $n ≥ 3$, and let $u$, $v$, $w$ be three distinct vertices of $K_n$. Determine the number of distinct paths from $u$ to $v$ that do not contain the vertex $w$.
User Avatar
213
views
1 answers
0 votes
Practice Material Question
If G is a connected graph with 6 vertices and maximum number of edges, then which of the following is true ? (a) Euler path exists, but Euler circuit does not exist ... in G.(c) Euler circuit does not exists in G(d) G is not traversable.
User Avatar
189
views
1 answers
0 votes
#algorithm
how many spanning trees are possible for complete graph of 4 vertices
User Avatar
3.6k
views
2 answers
3 votes
GATE CSE 2024 | Set 2 | Question: 7
Let $\text{A}$ be the adjacency matrix of a simple undirected graph $\text{G}$. Suppose $\text{A}$ is its own inverse. Which one of the following ... perfect matching$\text{G}$ is a complete graphThere is no such graph $\text{G}$
User Avatar
2.6k
views
1 answers
1 votes
GATE CSE 2024 | Set 2 | Question: 41
Let $\text{G}$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $\text{G}$ has even weight. ... have even weight $\text{OR}$ all edges in $\text{C}$ have odd weight
User Avatar
2.6k
views
4 answers
2 votes
GATE CSE 2024 | Set 2 | Question: 50
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.
User Avatar
2.7k
views
2 answers
4 votes
GATE CSE 2024 | Set 1 | Question: 24
The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ is _________.
User Avatar
2.7k
views
2 answers
2 votes
GATE CSE 2024 | Set 1 | Question: 41
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$ ... $k(k-1) / 2$ edges$G$ contains a vertex of degree at least $k$
User Avatar
833
views
1 answers
13 votes
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 15
Let $\mathrm{G}$ be a simple undirected graph on 8 vertices such that there is a vertex of degree 1 , a vertex of degree 2 , a vertex of degree 3 , ... the following can be the degree of the last vertex? (Select all that are possible)0348
User Avatar
673
views
1 answers
7 votes
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 57
A strongly connected component $(\mathrm{SCC})$ of a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ is a maximal set of vertices such that any two vertices in ... acyclic graph $G^{\prime}$ be $A, B$ respectively, then what is $A+B?$
User Avatar
170
views
0 answers
1 votes
Memory Based GATE DA 2024 | Question: 64
Minimum Number of colors in concentric circles.
User Avatar
559
views
1 answers
3 votes
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 63
For an undirected graph $G$, let $\overline{G}$ refer to the complement (a graph on the same vertex set as $G$, with $(i, j)$ as an edge in $\overline{G}$ if and ... v).(i) is equivalent to (ii) and (iv).(i) is equivalent to (ii) and (v)
User Avatar
784
views
1 answers
4 votes
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 46
Assume the following graph is a labeled graph i.e. every vertex has a unique label.In how many ways can we color the following labeled graph $\mathrm{G}$ with ... such that no two adjacent vertices are assigned the same color?
User Avatar
556
views
1 answers
3 votes
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 11
The figure above shows an undirected graph with six vertices. Enough edges are to be deleted from the graph in order to leave a spanning tree, which is a ... having the same six vertices and no cycles. How many edges must be deleted?
User Avatar
322
views
1 answers
0 votes
Made Easy Mock Test 2
User Avatar
241
views
1 answers
0 votes
ISRO 2024
Maximum number of Simple graphs possible with $n$ vertices$2^{n(n-1)/2}$2^{(n-1)/2}$2^{n(n+1)/2}$2^{n(n+1)}$
User Avatar
347
views
1 answers
0 votes
ISRO 2024
If there are five faces and nine vertices in an undirected planar graph, then number of edges is14612None of the above
User Avatar
572
views
2 answers
0 votes
ISRO 2024
Which of the following are true ?In a graph G with n' vertices and e' edges, sum of degrees of vertices = 2*e.Eccentricity of a connected graph can never be equal to ... ii), (iii)(ii), (iii), (iv)(i), (iii), (iv)None of the above
User Avatar
244
views
0 answers
0 votes
Which study material to refer to so that one can solve the theory questions on Graphs topic asked in PYQs
I have not been able to answer many of the Graph theory questions, I feel my comprehension of the topic is inadequate, could someone guide me to some reference material I could use to fill in the gaps, Thank you!
User Avatar
162
views
0 answers
0 votes
Find the MIS and MaxIS
User Avatar
150
views
1 answers
0 votes
#self doubt
Domination set and MIS are the same?
User Avatar
651
views
1 answers
0 votes
Regular and complete graph
which of the following statements is true:a complete graph is $(N-1)$ regulara $(N-1)$ regular is a complete graph
User Avatar
274
views
0 answers
0 votes
#self_doubt#pyq#graphtheory
Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal tothe answer is 45 ... be the answer?1- if the graph is directed 2- if vertices are not labeled.
User Avatar
312
views
1 answers
0 votes
#applied course
how many regions are in the above graph and please explain with region formula also.r=e-v+(c+1)my attempt is :r=5-5+2r=2but the rule is twice the no of ... ) = sum of region degrees which (4+5=9 ) can someone explain where the fault is
User Avatar
396
views
1 answers
0 votes
made easy test series
Suppose A is a 12 by 9 incidence matrix from a connected (but unknown) graph with 9 nodes and 12 edges. The diagonal entries of $A^{T}.A$give the number of edges into each node. Then, what is the sum of those diagonal entries ________.
User Avatar
Page: