68 views
Matching and edge coloring are same ?
no,they are not same

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.

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. :)