The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
ACE Bits And Bytes
+1
vote
172
views
Number of perfect matching in W
_{n }
(n>=4 and n is even) _________.
graphtheory
graphmatching
gate2019
asked
Jul 24, 2018
in
Graph Theory
by
abhishek1995_cse

172
views
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
+4
votes
Perfect Matching means degree of every vertex is 1
No perfect matching exist for wheel graph when no.of vertices are odd ( think about it )
In a wheel graph with n vertices(even), there are n1 vertices in cycle and one wheel vertex connected to remaining all vertices.
For matching that wheel vertex , we have n1 vertices===> possibilities are n1
Remaining n2 (even) matched with other neighbour ===> only one possibility.
Total possibilities = (n1)*1 = (n1)
answered
Jul 24, 2018
by
Shaik Masthan
comment
Please
log in
or
register
to add a comment.
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
0
votes
1
answer
1
ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.
asked
Jul 24, 2018
in
Graph Theory
by
abhishek1995_cse

280
views
graphtheory
graphconnectivity
+1
vote
1
answer
2
Ace Test Series: Graph Theory  Matching
my answer is C but the answer given is A someone please explain
asked
Jan 20, 2018
in
Graph Theory
by
ashish pal

138
views
acetestseries
graphtheory
graphmatching
0
votes
1
answer
3
CMI2018A9
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multitalented ... : Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
asked
Sep 14, 2019
in
Graph Theory
by
gatecse

92
views
cmi2018
graphtheory
graphconnectivity
graphmatching
independentset
descriptive
+1
vote
0
answers
4
GeeksforGeeks
Let G be a graph with no isolated vertices, and let M be a maximum matching of G. For each vertex v not saturated by M, choose an edge incident to v. Let T be the set of all the chosen edges, and let L = M ∪ T. Which of the following option is TRUE? A L is always ... G. B L is always a minimum edge cover of G. C Both (A) and (B) D Neither (A) nor (B) Can anyone pls help solving this?
asked
Jan 31, 2019
in
Graph Theory
by
Ashish Goyal

185
views
graphmatching
discretemathematics
graphtheory
testseries
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
Recent Posts
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
IIT Tirupati MS Interview 2020
IIT Bombay Mtech RA  interview experience (2020)
Subjects
All categories
General Aptitude
2k
Engineering Mathematics
8.2k
Discrete Mathematics
5.9k
Mathematical Logic
2.1k
Set Theory & Algebra
1.5k
Combinatory
1.4k
Graph Theory
846
Probability
1k
Linear Algebra
732
Calculus
600
Digital Logic
2.9k
Programming and DS
5k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.2k
Operating System
4.6k
Databases
4.2k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.2k
Others
1.5k
Admissions
595
Exam Queries
562
Tier 1 Placement Questions
23
Job Queries
71
Projects
19
Unknown Category
1k
Recent Blog Comments
Can someone tell me how to check part B marks?...
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,487
answers
201,823
comments
95,294
users