GATE CSE
First time here? Checkout the FAQ!
x
0 votes
68 views
Matching and edge coloring are same ?
asked in Graph Theory by (341 points)   | 68 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.6k 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. :)


Top Users Sep 2017
  1. Habibkhan

    7194 Points

  2. Warrior

    2686 Points

  3. Arjun

    2594 Points

  4. rishu_darkshadow

    2568 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,164 questions
33,743 answers
79,994 comments
31,124 users