$\begingroup$
$\endgroup$
5
I have a quick question.
The maximum matching problem is an easy problem but not a trivial one. I was wondering that if the bipartite graph was complete, is it a trivial problem?
I think we can just select an arbitrary edge $\{u,v\}$ and remove the vertices $u$ and $v$ from the graph and continue until there is no vertices.
-
$\begingroup$ By a complete bipartite graph, do you mean that there exist two disjoint sets of vertices where no two vertices in the same set have an edge between them but any two vertices from different sets do have an edge between them? There are no complete bipartite graphs with more than two vertices. $\endgroup$Fricative Melon– Fricative Melon2016年01月18日 17:02:20 +00:00Commented Jan 18, 2016 at 17:02
-
$\begingroup$ As you said, I mean this: there exist two disjoint sets of vertices where no two vertices in the same set have an edge between them but any two vertices from different sets do have an edge between them. $\endgroup$Brika– Brika2016年01月18日 17:17:15 +00:00Commented Jan 18, 2016 at 17:17
-
2$\begingroup$ @user1657355 The term "complete bipartite graph" is completely standard, with the meaning you give. $\endgroup$David Richerby– David Richerby2016年01月18日 17:51:43 +00:00Commented Jan 18, 2016 at 17:51
-
$\begingroup$ What have you tried? Have you tried working through some examples to see if you see a pattern? If yes, have you tried making a guess and then tried proving it? $\endgroup$D.W.– D.W. ♦2016年01月18日 20:04:48 +00:00Commented Jan 18, 2016 at 20:04
-
$\begingroup$ What I tired is in the question. $\endgroup$Brika– Brika2016年01月18日 20:31:44 +00:00Commented Jan 18, 2016 at 20:31
1 Answer 1
$\begingroup$
$\endgroup$
Yes, that would work. Instead of continuing until you have no vertices, though, you should continue until you have no edges. You may have vertices left over, if the two sets have different sizes.
answered Jan 18, 2016 at 17:35