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
0
votes
1
answer
Made Easy Workbook
What will be the number of components?
answered
2 days
ago
in
Graph Theory
by
zxy123
(
2.9k
points)

27
views
workbook
0
votes
1
answer
What is total number of planer graph can be formed with 6 vertices ?
answered
4 days
ago
in
Graph Theory
by
zxy123
(
2.9k
points)

29
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
(
287
points)

35
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)

20
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
(
645
points)

30
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)

8
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)

86
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)

50
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
StoneHeart
(
735
points)

33
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)

15
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
(
47
points)

29
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
(
717
points)

35
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
(
717
points)

33
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)

44
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
(
717
points)

22
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
(
717
points)

13
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
(
717
points)

106
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)

74
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
(
717
points)

25
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)

22
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
(
717
points)

19
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)

39
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
(
717
points)

17
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
(
717
points)

20
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
(
717
points)

25
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
(
717
points)

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

31
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
(
717
points)

24
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
(
717
points)

23
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
(
717
points)

34
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)

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

18
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
(
5
points)

22
views
0
votes
0
answers
Matching Number
Please tell me what is the Independence Number Domination Number Matching Number Covering Number of the given graph in the picture. Does perfect matching exist in the given graph?
asked
May 7, 2020
in
Graph Theory
by
Abhipsa
(
5
points)

30
views
discretemaths
graphtheory
0
votes
0
answers
Graph theory 3Ordered trees possible for a given no of nodes
asked
Apr 28, 2020
in
Graph Theory
by
ramcharantej_24
(
13
points)

24
views
trees
combinatory
graphtheory
discretemaths
graph
0
votes
0
answers
GATE201238 Video Solution
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 to $15$ $30$ $90$ $360$
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
569
points)

16
views
gate2012
graphtheory
normal
markstoall
counting
videosolution
0
votes
0
answers
GATE19941.6, ISRO200829 Video Solution
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
asked
Apr 18, 2020
in
Graph Theory
by
admin
(
569
points)

6
views
gate1994
graphtheory
combinatory
normal
isro2008
counting
videosolution
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 Jan 11  17
zxy123
450 Points
Abhisheksmile94
78 Points
kalin
60 Points
donniedarko
16 Points
Abhineet Singh
8 Points
Allica
8 Points
Shaik Masthan
8 Points
Enolx.21
6 Points
Sahil91
6 Points
aditi19
6 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
8,957
questions
3,118
answers
14,337
comments
95,787
users