The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Matching and edge coloring are same ?
asked in Graph Theory by (391 points) | 87 views
no,they are not same

1 Answer

+2 votes

MATCHING and EDGE COLORING are different things:-

i given here both definitions:-

MATCHING- matching in the simple graph is the subset of set of edges of a graph such that the no two edges are incident with same vertex.

EDGE COLORING- edge coloring of a graph is an assignment of colors to edges so that edges incident with a common vertex are assigned different colors.


answered by Loyal (2.9k points)
please give the example of matching

hi Harikesh, we take a example W4(wheel-4) for matching.


we first make a set of edges ,

i.e.   E = {{p,q},{p,r},{p,t},{r,t},{r,s},{s,q},{s,t},{q,t}}

according to definition of MATCHING: we make a subset of set E such that no two edges are incident on same vertex.

so, here there will be 10 MATCHINGS  of this graph.

MATCHING:1   {{p,q},{r,s}}                            

MATCHING:2   {{p,r},{s,q}}              

MATCHING:3   {{p,t},{r,s}}    

MATCHING:4  {{p,t},{s,q}}

MATCHING:5   {{r,t},{s,q}}                              

MATCHING:6   {{r,t},{p,q}}        

MATCHING:7   {{s,t},{p,q}}                                    

MATCHING:8   {{s,t},{p,r}}

MATCHING:9   {{q,t},{p,r}}                                     

MATCHING:10   {{q,t},{r,s}}                                 

Thank you. :)

Related questions

0 votes
0 answers
asked ago in Graph Theory by rahul sharma 5 Veteran (17.3k points) | 23 views
+3 votes
1 answer

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

28,834 questions
36,686 answers
34,640 users