Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [matching-theory]

For questions about matchings in graphs.

The study of matchings in graphs (bipartite and otherwise). A matching in a graph is a collection of edges no two of which share a common vertex. Common questions are the maximum size of a matching in a graph, the existence of matchings satisfying certain conditions, as well as structures on the set of all matchings.

554 questions
1
vote
0 answers

Maximal vs. maximum sized matchings

This question should be an easy one :) I couldn't find it already in stackexchange so thought it would be worth asking. As I understand it: A Maximal Matching cannot be extended (i.e. it is not a subset of any other matchings). A Maximum Sized…
JFreeman
  • 173
1
vote
0 answers

Prove that $A \in \mathcal{I}(\mathcal{A})$ and $B\subseteq A$ implies $B\in\mathcal{I}(\mathcal{A})$.

I tried finding stuff online but I couldn't about partial matchings. Definition we're given: A partial matching of $\mathcal{A}$ is a matching of some subfamily $\mathcal{B}\subseteq \mathcal{A}$. A matching is defined: A matching of $\mathcal{A}$…
OneGapLater
  • 820
  • 1
  • 9
  • 22
0
votes
1 answer

Showing that there's no matching of G that matches all v's of V1

I need to show that there's no matching of $G$ that matches all of the vertices of $V_1$, using Hall's Theorem. So Hall's Theorem is when $|X|$ is less than or equal to $|N(X)|$ (neighbours of the vertices in $X$) so if $X$ is $V_1$ then $X =…
Grand Skunk
  • 3
0
votes
0 answers

Maximum matching in a hamilton graph of "k" vertices is always (k+1)/2 , is this claim correct?

My observation is : - Say for a(any) Hamilton graph of 1000 vertices , the value of its maximum matching will be 500 . Can somebody prove it or verify it ?
user768815
  • 23