Not a Vertex Cover?

Computer Science Level 1

Which of the following graphs do not show a vertex cover ? (The vertices in the vertex cover are red).

A

B

C

D

E

A B C D E

View wiki
Karleigh Moore by Karleigh Moore , 27, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Karleigh Moore
Jul 5, 2016

In graph C there are some edges which do not touch a red vertex (shown in blue).

5 Helpful 0 Interesting 0 Brilliant 5 Confused

Isnt' D also not a vertex cover? The bottom left edge is not covered by any red vertex.

Daniele Maccari - 4 years, 3 months ago

Log in to reply

I agree. D is not a vertex cover.

Siva Budaraju - 3 years, 11 months ago

@Daniele Maccari @Siva Budaraju - I also agree: (D) is not a node cover of the graph.

Wesley Zumino - 3 years, 11 months ago

Indeed, D is also not a vertex cover.

Manuja Desilva - 2 years, 6 months ago

No, D is vertex cover.

Lakshman Patel - 1 year, 9 months ago

Log in to reply

No, it is not

Elliot Liu - 1 year, 3 months ago

D is not a vertex cover because of the edge of "bottom middle" and "bottom left". Either "bottom middle" or "bottom left" needs to be in vertex cover, or, in this case, be red.

Felthiel Evershade - 1 year ago
Nawfel Giuma
Nov 24, 2019

theres one edge in d that has no vertices on V

2 Helpful 0 Interesting 2 Brilliant 0 Confused

Yes, D is also not a vertex cover

Sakshi Sharma - 1 year, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...