Vertex Cover

 

1. Vertex Cover Definition
2. Vertex Cover ≤ρ Clique
3. Clique ≤ρ Vertex Cover
4. Vertex Cover ϵ NP

1) Vertex Cover:

Definition: - It represents a set of vertex or node in a graph G (V, E), which gives the connectivity of a complete graph

According to the graph G of vertex cover which you have created, the size of Vertex Cover =2

2) Vertex Cover ≤ρ Clique

In a graph G of Vertex Cover, you have N vertices which contain a Vertex Cover K. There must exist of Clique Size of size N-K in its complement.

According to the graph G, you have
Number of vertices=6
Size of Clique=N-K=4

You can also create the Clique by complimenting the graph G of Vertex Cover means in simpler form connect the vertices in Vertex Cover graph G through edges where edges don?t exist and remove all the existed edges

You will get the graph G with Clique Size=4

3) Clique ≤ρ Vertex Cover

Here through the Reduction process, you can get the Vertex Cover form Clique by just complimenting the Clique graph G within the polynomial time.

4) Vertex Cover ϵ NP

As you know very well, you can get the Vertex Cover through Clique and to convert the decision-based NP problem into Clique firstly you have to convert into 3CNF and 3CNF into SAT and SAT into CIRCUIT SAT that comes from NP.

Proof of NPC:-

1. Reduction from Clique to Vertex Cover has been made within the polynomial time. In the simpler form, you can convert into Vertex Cover from Clique within the polynomial time
2. And verification has also been done when you convert Vertex Cover to Clique and Clique to 3CNF and satisfy/verified the output within a polynomial time also, so it concluded that Reduction and Verification had been done in the polynomial time that means Vertex Cover also comes in NPC