0
$\begingroup$

Let G = (V,E) be a connected graph and a ∈ V be an articulation point of G. How can be proved that there is an edge e ∈ G incident with a with the property that e doesn't belong to a perfect matching of G?

Let's say that there are two vertices u,v ∈ G so that the only paths between them go through a. Then there is no edge directly connecting u and v. It means that a has at least 2 vertices(which is pretty obvious) and knowing that the property of a perfect matching is that the degree of any vertex is equal to 1, it means that there is at least one edge incident to a that doesn't belong to the perfect matching. But I'm not sure, is it okay?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.