Register
Webpage for Graph Theory:

Recent questions tagged graph-theory

10 votes
5 answers
813
ISRO2011-35
How many edges are there in a forest with $v$ vertices and $k$ components? $(v+1) - k$ $(v+1)/2 - k$ $v - k$ $v + k$
How many edges are there in a forest with $v$ vertices and $k$ components?$(v+1) - k$$(v+1)/2 - k$$v - k$$v + k$
User Avatar
3 votes
4 answers
815
maximum number of edges in a graph with components
A graph G have 9 vertices and two components. What is the maximum number of edges possible in this graph?
A graph G have 9 vertices and two components. What is the maximum number of edges possible in this graph?
User Avatar
4 votes
4 answers
816
graph coloring
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also
User Avatar
2 votes
1 answer
817
Properties of Planar graph
Can anyone explain a connected planar graph with n vertices and e edges has e-n+2 regions??
Can anyone explain a connected planar graph with n vertices and e edges has e-n+2 regions??
User Avatar
3 votes
2 answers
818
graphs - bipartite
Q) For what value of n Kn can be bipartite a)2 b)3 c)4 d) 5
Q) For what value of n Kn can be bipartitea)2b)3c)4d) 5
User Avatar
33 votes
9 answers
819
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_______________.
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_______________.
User Avatar
28 votes
6 answers
821
GATE CSE 2015 Set 2 | Question: 28
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ is A multiple of 4 Even Odd Congruent to 0 $mod$ 4, or, 1 $mod$ 4.
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ isA multiple of 4EvenOddCongruent to 0 $mod$ 4...
User Avatar
0 votes
2 answers
822
maths_mock_test2
User Avatar
5 votes
1 answer
823
maths_mock_test
How many labelled sub-graphs of $K_n$ are isomorphic to $W_{n-1}$? (Where $K_n$ : Complete graph with $n$ vertices , $W_n$ : Wheel graph with $ n+1$ vertices) 1.$\frac{(n-1)!}{2}$ 2. $\frac{(n-2)!}{2}$ 3. $\frac{n!}{2(n-1)}$ 4. $\frac{n!}{2(n-1)^2}$
How many labelled sub-graphs of $K_n$ are isomorphic to $W_{n-1}$?(Where $K_n$ : Complete graph with $n$ vertices , $W_n$ : Wheel graph with $ n+1$ vertices)1.$\frac{(n-1...
User Avatar
1 votes
1 answer
824
Number of distinct graphs
Number of distinct graphs with p vertices and q edges ( p not equal to q) is always equal to a) p b) q c)min(p,q) d)max (p,q) e) none of this
Number of distinct graphs with p vertices and q edges ( p not equal to q) is always equal toa) pb) qc)min(p,q)d)max (p,q)e) none of this
User Avatar
0 votes
1 answer
825
Consider the following set : {1,2,3,.....n}. Now consider all possible subset. Two subset S1 and S2 are having edge between them only if their intersection has two common elements.
Consider the following set : {1,2,3,.....n}. Now consider all possible subset. Two subset S1 and S2 are having edge between them only if their intersection has two common...
User Avatar
16 votes
3 answers
827
number of perfect matching in complete graph
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
User Avatar
4 votes
2 answers
828
No of vertices in Planar graph
If G is a planar graph with 35 regions each of degree 6 the no of vertices are a) 70 b) 80 c) 72 d) 62 What does degree of a region specify here?
If G is a planar graph with 35 regions each of degree 6 the no of vertices area) 70 b) 80 c) 72 d) 62What does degree of a region specify here?
User Avatar
34 votes
2 answers
830
GATE IT 2004 | Question: 37
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$? $10$ $11$ $18$ $19$
What is the number of vertices in an undirected connected graph with $27$ edges, $6$ vertices of degree $2, 3$ vertices of degree $4$ and remaining of degree $3$?$10$$11$...
User Avatar
25 votes
8 answers
831
GATE IT 2004 | Question: 5
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices?$n-1$$n$$n+1$$2n-1$
User Avatar
37 votes
7 answers
833
GATE IT 2006 | Question: 11
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is aHamiltonian cyclegri...
User Avatar
73 votes
6 answers
834
GATE IT 2007 | Question: 25
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ?$1$$2$$3$$n$
User Avatar
43 votes
6 answers
835
GATE IT 2008 | Question: 27
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph is sure to be regular complete Hamiltonian Euler
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph...
User Avatar
34 votes
4 answers
836
GATE IT 2008 | Question: 3
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
What is the chromatic number of the following graph? $2$$3$$4$$5$
User Avatar
19 votes
3 answers
837
GATE CSE 1995 | Question: 24
Prove that in finite graph, the number of vertices of odd degree is always even.
Prove that in finite graph, the number of vertices of odd degree is always even.
User Avatar
33 votes
5 answers
838
GATE CSE 1995 | Question: 1.25
The minimum number of edges in a connected cyclic graph on $n$ vertices is: $n-1$ $n$ $n+1$ None of the above
The minimum number of edges in a connected cyclic graph on $n$ vertices is:$n-1$$n$$n+1$None of the above
User Avatar
19 votes
3 answers
840
GATE CSE 1994 | Question: 2.5
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________
User Avatar
Page: