First time here? Checkout the FAQ!
0 votes
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
31,124 users