# How to solve this problem using the Maximum matching algorithm for general graph?

For any general graph G(V,E) , the maximum matching can be calculated in O(√V.|E|) time using the following algorithm :

https://www.researchgate.net/publication/221499631_An_Osqrtv_E_Algorithm_for_Finding_Maximum_Matching_in_General_Graphs

The following problem has 5-parts : -

1)Calculate maximum matching of Graph G

Can Tutte Matrix be used here ?

2)Calculate maximum matching of Graph G1 where G1 is the Line-Graph of graph G

3)Calculate maximum matching of Graph G2 where G2 is the Line-Graph of graph G1

4)Calculate maximum matching of Graph G3 where G3 is the Line-Graph of graph G2

5)Calculate maximum matching of Graph G4 where G4 is the Line-Graph of graph G3

Part-1 can be solved using the algorithm above.

My approach for solving part-2 is to construct G1 and then apply the algorithm on it , same for G2,G3,G4 , but the problem is that number of nodes and edges increase a lot in G1,G2,G3,G4 , if say , G has 3000 nodes and same number of edges, G3 might have more than 108/109 nodes and edges , so I cannot construct such a large graph as it will be inefficient in time and space to do it . How can solve the remaining parts efficiently ?

• Perhaps this will help: sciencedirect.com/science/article/pii/S0012365X97001039 Apr 7, 2020 at 9:19
• Thanks.... But I did not understand the meaning of 2-chain graph cover as they mentioned in the article. Can you answer it here : math.stackexchange.com/questions/3613889/… or explain me in the comments. Apr 7, 2020 at 12:18
• I believe it's just a path of length 2 (edges). Apr 7, 2020 at 12:34
• But what is the exact meaning of "2-chain-graph-cover" . So confusing :( Apr 7, 2020 at 15:03
• All of these concepts, including 2-chain, are defined in the paper. Apr 7, 2020 at 15:21