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?


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.