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
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
in
Graph Theory
by
mayureshpatle
(
855
points)

63
views
0
votes
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
in
Graph Theory
by
Shaik Masthan
(
1.4k
points)

35
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
in
Graph Theory
by
Shashank Rustagi
(
513
points)

28
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
in
Graph Theory
by
Vishal_kumar98
(
7
points)

13
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
in
Graph Theory
by
Sherrinford03
(
73
points)

19
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
in
Graph Theory
by
Scion_of_fire
(
47
points)

24
views
aceacademytestseries
engineeringmathematics
gatepreparation
gate
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
in
Graph Theory
by
Nikhil_dhama
(
151
points)

33
views
graphtheory
gate
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
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

25
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
in
Graph Theory
by
Arkaprava
(
711
points)

30
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
in
Graph Theory
by
Arkaprava
(
711
points)

30
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
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

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

21
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
in
Graph Theory
by
Arkaprava
(
711
points)

11
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
in
Graph Theory
by
Arkaprava
(
711
points)

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

59
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
in
Graph Theory
by
Arkaprava
(
711
points)

23
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
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

17
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
in
Graph Theory
by
Arkaprava
(
711
points)

17
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
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

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

12
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
in
Graph Theory
by
Arkaprava
(
711
points)

12
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
in
Graph Theory
by
Arkaprava
(
711
points)

23
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
in
Graph Theory
by
Arkaprava
(
711
points)

14
views
graphtheory
discretemaths
0
votes
1
answer
Self doubt GRAPH THEORY
answered
Aug 12
in
Graph Theory
by
Arkaprava
(
711
points)

29
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
in
Graph Theory
by
Arkaprava
(
711
points)

20
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
in
Graph Theory
by
Arkaprava
(
711
points)

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

32
views
discretemaths
graphtheory
gatepreparation
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
in
Graph Theory
by
jayeshasawa001
(
2.5k
points)

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

17
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
in
Graph Theory
by
Abhipsa
(
5
points)

20
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
in
Graph Theory
by
Abhipsa
(
5
points)

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

19
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
in
Graph Theory
by
admin
(
193
points)

12
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
in
Graph Theory
by
admin
(
193
points)

3
views
gate1994
graphtheory
combinatory
normal
isro2008
counting
videosolution
0
votes
0
answers
GATE2014151 Video Solution
Consider an undirected graph $G$ where selfloops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
asked
Apr 18
in
Graph Theory
by
admin
(
193
points)

7
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
videosolution
0
votes
0
answers
GATE201830 Video Solution
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is ... $\mid ij \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
asked
Apr 18
in
Graph Theory
by
admin
(
193
points)

5
views
gate2018
graphtheory
graphsearch
normal
videosolution
0
votes
0
answers
GATE200723 Video Solution
Which of the following graphs has an Eulerian circuit? Any $k$regular graph where $k$ is an even number. A complete graph on $90$ vertices. The complement of a cycle on $25$ vertices. None of the above
asked
Apr 18
in
Graph Theory
by
admin
(
193
points)

6
views
gate2007
graphtheory
normal
graphconnectivity
videosolution
0
votes
0
answers
GATE20021.25, ISRO200830, ISRO20166 Video Solution
asked
Apr 18
in
Graph Theory
by
admin
(
193
points)

11
views
gate2002
graphtheory
easy
isro2008
isro2016
graphconnectivity
videosolution
0
votes
0
answers
GATE200336 Video Solution
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
asked
Apr 18
in
Graph Theory
by
admin
(
193
points)

3
views
gate2003
graphtheory
graphmatching
normal
videosolution
0
votes
0
answers
GATE2016203 Video Solution
The minimum number of colours that is sufficient to vertexcolour any planar graph is ________.
asked
Apr 18
in
Graph Theory
by
admin
(
193
points)

4
views
gate20162
graphtheory
graphcoloring
normal
numericalanswers
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
2020 Oct 26  Nov 01
shweta._.5
71 Points
mayureshpatle
66 Points
Ashutosh777
8 Points
vizzard110
8 Points
user2525
6 Points
Shivateja MST
4 Points
rish1602
2 Points
RasMalai
2 Points
Shaik Masthan
2 Points
Sinchit
2 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
Recent Blog Comments
Thanks, Can you tell me till when this might get...
Recent questions and answers in Graph Theory
8,430
questions
2,707
answers
13,232
comments
95,452
users