///
Considerando Problemas NP-Completos, temos as seguintes afirmativas:
I. Um clique em um grafo não dirigido G = (V, E) é um subconjunto de vértices, no qual cada par está ligado por uma aresta em E. Em outras palavras, um clique é um subgrafo completo de G. O tamanho de um clique é o número de vértices que ele contém. O problema do clique é o problema de otimização de encontrar um clique de tamanho máximo em um grafo.
II. Uma cobertura de vértices de um grafo não dirigido G = (V, E) é um subconjunto V' ⊆ V tal que (u,v) ∈ E, então u ∈ V' ou v ∈ V' (ou ambos). Isto é, cada vértice "cobre" suas arestas incidentes, e uma cobertura de vértices para G é um conjunto de vértices que cobre todas as arestas em E. O tamanho de uma cobertura de vértices é o número de vértices que ele contém.
III. No problema do caixeiro-viajante, que está intimamente relacionado ao problema do ciclo hamiltoniano, um vendedor deve visitar cidades. Modelando o problema como um grafo completo com vértices, podemos dizer que o vendedor deseja fazer um percurso, ou um ciclo hamiltoniano, visitando cada cidade exatamente uma vez e terminando na cidade de onde partiu. O vendedor incorre em um custo inteiro não negativo c(i,j) para viajar da cidade i para a cidade j, e deseja fazer o percurso cujo custo total seja mínimo, em que o custo total é a soma dos custos individuais ao longo das arestas do percurso.
IV. O problema da soma de subconjuntos, temos um conjunto finito S de inteiros positivos e um inteiro alvo t > 0. Deseja-se saber se existe um subconjunto cuja soma de seus elementos é t.
V. Um passeio de Euler de um grafo conexo dirigido G = (V, E) é um ciclo que percorre cada aresta de G exatamente uma vez, embora possa visitar cada vértice mais de uma vez. É possível determinar se um grafo tem um passeio de Euler no tempo de apenas O(E) e, de fato, podemos encontrar as arestas do passeio de Euler no tempo O(E). Um ciclo hamiltoniano de um grafo dirigido G = (V, E) é um ciclo simples que contém cada vértice em V. Determinar se um grafo dirigido tem um ciclo hamiltoniano é NP-completo.
Acerca das afirmativas acima, podemos afirmar que: