What does it mean for an edge "to extend to a matching"?

487 Views Asked by At

I've got a problem that is defined as follows:

Let $G$ be a bipartite (undirected) gaph with vertex classes X, Y. Show that if $G$ has a matching covering every vertex of $X$, then there exists $x\in X$ such that every edge incident with x extends to a matching covering every vertex of $X$.

A matching is by definition a subset of the graphs edge set without common vertices. As such, all edges in the matching are not connected with each other. Because of that, I do not understand what it means for an edge to extend to a matching, as all the edges in a matching cannot be connected but the matching to which the edge "extends to" has to cover all vertices of $X$.

2

There are 2 best solutions below

1
On BEST ANSWER

In as many words, they mean that the union of all maximal matchings contains all the edges incident on some $x\in X$.

0
On

A matching which an edge "extends to" just means a matching which contains that edge as an element. In general, saying an object $a$ "extends to" an object $b$ typically means that $b$ "contains" $a$ in some sense that is dependent on context. (Your confusion here may be grammatical: when we say "$a$ extends to $b$", that is just a different way of saying "$b$ is an extension of $a$" or "$b$ extends $a$". English verbs can often be very flexible with their valency like this.)

In this case, the intuition is that you are building up a matching by adding one edge at a time, and so you can start with one edge and "extend" your construction by adding more edges to eventually reach a matching covering all vertices.