# Minimum Vertex Cover in Graphs

I was looking into this question: https://www.spoj.com/problems/PT07X/
I’m using the following algorithm: https://paste.ubuntu.com/23221571/

But this is failing for the below condition:
6
1 2
2 3
3 4
4 5
5 6

Output: 3
Correct Solution: 2

Am i missing something?

Edited

why have u written 5 edges and 5 nodes in the input ?

Sorry, that’s *6

6
1 2
2 3
3 4
4 5
5 6

Then correct output should be 3 because for 6 nodes you can see the image for one of the optimal solutions

Now for your solution I made some changes and also commented the logic also and it gave AC . Hope u understand them , if not then feel free to ask

In the above graph, if you select 2 and 5 as the nodes, every other node will have an edge connecting to the selected nodes. Hence minimum vertex would be 2, right?

Your Code Changed a Bit works!

For the case:

6
1 2
2 3
3 4
4 5
5 6

It is giving 3 as output but 2 is the correct solution.

if u select 2 and 5 as MVC then the edge connecting 3 and 4 would not be belonging to any selected vertex

Correct. But I need the nodes that connects to every other node. Correct me if I got it wrong with MVC. I’m trying to figure out a use case where I need to find the nodes that are connected to every other node through an edge.

For example, in the graph you posted, if I select 2 and 5, all my other nodes (1,3,4,6) are connected to 2 and 5.

no u have to see that if any of the endpoints of all edges should belong to the selected vertex set

That’s MVC right? So in my case (which is different from the question I posted), I need the minimum number of nodes directly connecting all other nodes in an undirected graph. I guess I mistook it for MVC.
My actual question is to find the minimum number of nodes directly connecting all other nodes in an undirected graph while MVC says that all edges has atleast one end point in subset.

Its 3 only

That’s for MVC, but i have a different question.