Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Blogs
Previous Year
Exams
Recent questions and answers in Graph Theory
+1
vote
0
answers
GATE graph theory
How many nonisomorphic graphs are possible with 6 edges 6 vertices each having a degree of 2? 2 4 5 6
asked
Mar 9
in
Graph Theory
by
donniedarko
(
39
points)

16
views
graphtheory
selfdoubt
0
votes
1
answer
Dominating set and Independent set.
Please explain the basic difference between Independent set and Dominating Set?
answered
Feb 24
in
Graph Theory
by
Dheera
(
14
points)

16
views
graphtheory
discretemaths
0
votes
0
answers
gate overflow book
https://gateoverflow.in/83854/gate19901viii The above is the link of the question. In the solution it was assumed that the graph is complete. But in the question nothing is mentioned. Also a complete graph doesn't contain self loops. So what I'm thinking is, if we ... the number of the edges in the graph, then m = n^2  m should be the condition. Please let me know about this!
asked
Feb 6
in
Graph Theory
by
hadarsh
(
5
points)

15
views
graph
+1
vote
1
answer
Ace Test Series
consider a cycle graph of 4 vertices and needs to perform the vertex coloring using 4 colors. The maximum number of vertex colorings possible is (Answer given as 68)
answered
Jan 24
in
Graph Theory
by
SarathBaswa
(
849
points)

24
views
graphtheory
0
votes
1
answer
Made Easy Workbook
What will be the number of components?
answered
Jan 14
in
Graph Theory
by
zxy123
(
3.6k
points)

46
views
workbook
0
votes
1
answer
What is total number of planer graph can be formed with 6 vertices ?
answered
Jan 12
in
Graph Theory
by
zxy123
(
3.6k
points)

38
views
graphtheory
discretemaths
0
votes
1
answer
TestBook Test Series
Consider G(V, E) be a complete undirected graph with 6 edges having a distinct weight from 1, 3, 9, 27, 81, and 243. Which of the following will NOT be the weight of them minimum spanning tree of G? (*This question may have multiple correct answers) A)121 B)13 C)40 D)31
answered
Jan 1
in
Graph Theory
by
wander
(
301
points)

43
views
discretemaths
0
votes
0
answers
Self doubt from graph coloring
A graph which not having even length cycle then 3 color are sufficient to color vertices of graph such that no two adjacent vertex having same color?
asked
Dec 27, 2020
in
Graph Theory
by
Vaishali Trivedi
(
5
points)

24
views
selfdoubt
0
votes
1
answer
#madeeasy #chromaticnumber
Which of the following options are not the chromatic polynomial of the following graph: a) b) c) d) can someone explains?
answered
Dec 26, 2020
in
Graph Theory
by
Sahil91
(
683
points)

32
views
madeeasytest
0
votes
0
answers
Made easy workbook
Let G be a Graph with V(G)={i1<=i<=4n} where V(G) is the set of vertices of G. such that two numbers x and y are adjacent iff (x+y) is a multiple of 4. Find the number of the connected component in graph G 2 4 N None of these From the above k components, assume that each component Ck has mk vertices, then what is the maximum value of mk in the graph n 2n 3n None of these
asked
Dec 8, 2020
in
Graph Theory
by
Gautam9596
(
5
points)

10
views
workbook
+1
vote
1
answer
National olympiad of informatics
Siruseri Traffic Lights Adapted from Traffic Lights, International Olympiad in Informatics, 1999 In Siruseri, there are junctions connected by roads. There is at most one road between any pair of junctions. There is no road connecting a junction to itself. The travel time for a road is the ... 3 to 2 to 4 takes time 8 + 0 (no wait) + 6 + 1 (wait till 15) + 10 = 25.
answered
Oct 12, 2020
in
Graph Theory
by
mayureshpatle
(
861
points)

91
views
+1
vote
1
answer
Self doubt  Graph Connectivity (NPTEL & PY)
Let G be a graph with n vertices and if every vertex has a degree of at least $\frac{n−1}{2}$ then G is connected. Source : https://gateoverflow.in/1221/gate200723 Let G be a graph with n vertices and if every vertex has a degree of at ... then G is connected. source : https://nptel.ac.in/courses/106/106/106106183/ My doubt : Which one is right?
answered
Sep 18, 2020
in
Graph Theory
by
Shaik Masthan
(
1.5k
points)

54
views
discretemaths
graphtheory
0
votes
1
answer
Self Doubt  Planar graph (PY)
$K_5$ is nonplanar. I am showing you my proof. Please tell me whether this is the right way or not to prove that $K_5$ is nonplanar. $\sum$ (deg)$=4+4+4+4+4=20$ $e=10$ and $n=5$ Assume $K_5$ is planar. $ve+r=2$ ... $K_5$ is nonplanar. If this is the right way, why this method didn't work in this graph. Source: https://gateoverflow.in/87129/gate19903vi
answered
Sep 16, 2020
in
Graph Theory
by
ijnuhb
(
747
points)

36
views
discretemaths
graphplanarity
graphtheory
selfdoubt
0
votes
0
answers
Ace Academy Practise Book
The chromatic number of a star graph with n vertices (n≥ 2) is ________.
asked
Sep 11, 2020
in
Graph Theory
by
Vishal_kumar98
(
37
points)

16
views
0
votes
1
answer
Previous year question
The maximum number of edges in a bipartite graph on 12 vertices is _________. Please tell any generalized solution for this problem, if exists.
answered
Sep 2, 2020
in
Graph Theory
by
Sherrinford03
(
73
points)

24
views
graphtheory
previousyearquestion
maths
0
votes
1
answer
ACE Academy test series Question
Number of cycles of length 4 that are possible in the complete bipartite graph K(4,6) is
answered
Sep 2, 2020
in
Graph Theory
by
Scion_of_fire
(
49
points)

41
views
aceacademytestseries
engineeringmathematics
gate2021
0
votes
1
answer
Previous question paper
Construct a graph G with the following properties: edge connectivity of G =4, Vertex connectivity of G=3, and degree of every vertex of G >=5.
answered
Aug 31, 2020
in
Graph Theory
by
Nikhil_dhama
(
151
points)

46
views
graphtheory
urgent
0
votes
1
answer
Trees self doubt
S1: A tree with n vertices which has no vertices of degree 2 must have at least leaves S2: The number of trees on 5 labelled vertices is 125. Which of the following statements is true? (A). Only S1 (B). Only S2 (C). Only S1 and S2 (D). None of the above
answered
Aug 16, 2020
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

26
views
graph
trees
graphtheory
0
votes
1
answer
kenneth rosen(chapter 10 ,theorem 5) 7th edition
theorem: HALL’S MARRIAGE THEOREMThe bipartite graph G=(V,E) with bipartite (v1,v2) has a complete matching from v1 to v2 if and only if N(A)$\geq$A for all subsets of A of V1. explain with example
answered
Aug 16, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

45
views
0
votes
1
answer
Kenneth Rosen7th editionChapter 10/10.8
THE FOUR COLOR THEOREM: The chromatic number of a planar graph is no greater than four. Question #40 (10.8) : Show that every planar graph G can be colored using six or fewer colors. Question #41 (10.8) : Show that every planar graph G ... is already stated in the four color theorem that we don't require more than 4 colors in order to color a planar graph.
answered
Aug 16, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

36
views
kennethrosen
graphtheory
0
votes
1
answer
Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Chapter 4 Question 27
answered
Aug 16, 2020
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

60
views
discretemaths
graphtheory
graphisomorphism
0
votes
2
answers
Are planar graphs and vertex and edge cover included in GATE 2021 syllabus?
answered
Aug 16, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

25
views
0
votes
1
answer
What is the degree of region?
What is the degree of region r4? How you find it?
answered
Aug 16, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

14
views
graphtheory
discretemaths
0
votes
3
answers
GATE 2020 graph theory
How many number of cut vertex in tree if n is the number total vertex in tree?
answered
Aug 16, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

112
views
0
votes
4
answers
#DM #Graphs labeled simple graphs
How to count number of labeled simple graphs? Please explain!
answered
Aug 16, 2020
in
Graph Theory
by
Akanksha Agrawal
(
309
points)

75
views
selfdoubt
graphtheory
graph
0
votes
1
answer
Kenneth Rosen Edition 7 Exercise 10.2 Question 44
Suppose that $d_{1}, d_{2}, ..., d_{n}$ is a graphic sequence. Show that there is a simple graph with vertices $v_{1}, v_{2}, …, v_{n}$ such that deg($v_{i}$) = $d_{i}$ for i = 1,2, …, n and $v_{1}$ is adjacent to $v_{2}, …, v_{d1 + 1}$.
answered
Aug 16, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

26
views
kennethrosen
graphtheory
0
votes
2
answers
#GrpaphTheory #self Doubt Degree of Self loop
what is Degree of Self loop in undirected graph? Is it 2 or 1? please give a proper source
answered
Aug 16, 2020
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

25
views
selfdoubt
0
votes
1
answer
Number of perfect matching in Kn?
Find number of perfect matching in Kn where n is even? Please explain too?
answered
Aug 16, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

23
views
discretemaths
graphtheory
0
votes
2
answers
#DM #SelfDoubt in previous year GATE
How many m len cycles in complete graph of n vertices? Please explain.
answered
Aug 16, 2020
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

42
views
selfdoubt
0
votes
2
answers
#Grpah Theory. #SelfDoubt
What are number of independent sets in Complete graph?
answered
Aug 15, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

18
views
selfdoubt
0
votes
1
answer
Find no of Hamiltonian cycles in kn,n
How many Hamiltonian cycles are there in complete bipartite graph K n,n
answered
Aug 15, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

43
views
hamiltoniangraph
graphtheory
combinatory
0
votes
1
answer
Proof of Euler equation
Euler equation is  V +R = E + 2 Can someone please show me how to come to above conclusion?
answered
Aug 15, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

27
views
discretemaths
graphtheory
0
votes
1
answer
Hamiltonian Graph
Consider the following Graphs: S1: Graph with vertices and each vertex has degree S2: Graph with 20 vertices such that for every 2 vertices Which of the following represents hamilton graph? (A). Only S1 (B). Only S2 (C). Both S1 and S2 (D). Neither S1 nor S2
answered
Aug 15, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

21
views
graphtheory
discretemaths
0
votes
1
answer
Self doubt GRAPH THEORY
answered
Aug 12, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

32
views
graphtheory
discretemathematics
discretemaths
discretemaths
0
votes
1
answer
Gatebook Test series doubt
The edge graph of a graph G is the graph with vertex set E(G) in which two vertices are joined if and only if they are adjacent edges in G. if G is a simple graph with degree sequence , the no of edges in edge graph of G is?
answered
Aug 12, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

27
views
0
votes
1
answer
Self doubt on graph theory
If we delete vertices from a graph, then what will happen to number of components ? will they increase or will remain same. Please answer my doubt.
answered
Aug 11, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

24
views
graphtheory
0
votes
1
answer
Why Euler circuit does not exist when number of odd degree vertices is 2
answered
Aug 10, 2020
in
Graph Theory
by
Arkaprava
(
801
points)

37
views
discretemaths
graphtheory
0
votes
1
answer
I think the answer made easy gave is incorrect
How can G1 and G2 be isomorphic as in G2 we have a node of degree 2 and in G1 there is no node of degree 2 .
answered
Aug 10, 2020
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

40
views
0
votes
0
answers
Textbook questions #doubt
What should be the answer?
asked
Jul 22, 2020
in
Graph Theory
by
premu
(
163
points)

20
views
graphtheory
0
votes
0
answers
adjacency matrix in graphs
A represents an adjacency matrix of Graph G The number of paths of length 8 from vertex 1 to vertex 4??
asked
May 8, 2020
in
Graph Theory
by
Abhipsa
(
17
points)

24
views
To see more, click for all the
questions in this category
.
Quick search syntax
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
2021 Apr 12  18
Bikram
12 Points
chirudeepnamini
4 Points
Weekly Top User (excluding moderators) will get free access to
GATE Overflow Test Series for GATE 2021
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
Recent questions and answers in Graph Theory
9,197
questions
3,182
answers
14,686
comments
96,162
users