# Recent questions tagged graph-matching

1 vote
1
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 multi-talented and each ... is: Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
1 vote
2
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 an edge cover of 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?
3
4
5
Consider the Bipartite graph shown. If four edges are chosen at random, what is the probability that they form a complete matching from V1 to V2 ? A. 0.039 B. 0.052 C. 0.071 D. 0.083
1 vote
6
Number of perfect matching in Wn (n>=4 and n is even) _________.
7
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect matching will have n/2 edges and there won't be any perfect matching if n is odd. I don't know whether i got it properly or not. Can please anybody explain the Perfect matching in a complete graph with simpler examples ?
1 vote
8
my answer is C but the answer given is A someone please explain
1 vote
9
Maximum no of edges in a triangle-free, simple planar graph with 10 vertices
10
11
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
1 vote
12
13
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For each edge, delete it from T if that edge belongs to a cycle in T. Assuming all the edge costs are distinct, does this new algorithm correctly compute a MST? a) Yes b) no c) cant say
14
What are the chromatic number of following graphs? Answer is 6 and 4 respectively.But i am getting 3 for both. Please someone confirm this?
15
When matching number and covering number are same then can we say that it is a perfect matching case?Do i need to check the elements of the set( edges in both matching and covering) also if their cardinality is same?If yes,then can someone give me an example where matching number ... number same but still it is not a perfect match?I am not able to find such a case and i think it will not exist.
16
In a village there are equal no of boys and girls of marriageable age.Each boy dates a certain no. of girls and each girl dates a certain number of boys,under what condition is it possible that every girl and boy gets married to one of their dates?
17
Please explain how perfect matching in given tree is 1? Why not 3 with edges ab,ce,df?
18
Find the matching number for the given graph-
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$