Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Vertex Cover in Cubic Graph

2 views
Skip to first unread message

Jason

unread,
Feb 20, 2009, 8:21:57 PM2/20/09
to

Hi Everyone,

I need to proof Vertex Cover problem is NP complete even for cubic
graphs. Notice that a cubic graph is a graph such that every vertex
has degree of *exactly three*. I found one paper but his definition
for cubic graph is a little loose in that the degree can be less than
3.

Can anybody give me a hint?

Thanks!

Jason

0 new messages