2024-177

Considere o grafo \(G\) com os seguintes vértices e arestas:
\[V(G)=\{A,B,C,D,E,F\}\]

\[E(G)=\{(A,B),(A,C),(A,D),(B,C),(B,D),(C,D),(C,E),(D,E),(D,F),(E,F)\}\]

Qual das alternativas a seguir é correta?

a) \(G\) é planar, possui número cromático 3, e contém um ciclo hamiltoniano: \(A\)-\(B\)-\(C\)-\(D\)-\(E\)-\(F\)-\(A\).

b) \(G\) não é planar, possui número cromático 4, e não contém um ciclo hamiltoniano.

c) \(G\) é planar, possui número cromático 3, e não contém um ciclo hamiltoniano.

d) \(G\) é planar, possui número cromático 4, e contém um ciclo hamiltoniano: \(A\)-\(D\)-\(C\)-\(E\)-\(F\)-\(B\)-\(A\).

e) N.D.A.

ideia original de: Glaymar A. França

2024-172

 Considere o grafo abaixo:

Quais das afirmações abaixo estão corretas?

I - O grafo acima é planar;

II - O grafo acima possui um ciclo hamiltoniano;

III - o grafo acima é euleriano;

a) I, II e III;

b) I e II;

c) II  e III;

d) I  e III;

e) NDA;

Ideia original de: Gabriel S. Kraszczuk

2024-169

 Considere as afirmações abaixo a respeito do grafo de Petersen e assinale a alternativa correta: 

I) O grafo de Petersen não é planar. 

II) O grafo de Petersen possui crossing number = 2 (lembrando que o crossing number é o menor número de cruzamentos de arestas que se pode obter ao desenhar o grafo em um plano).

III) O grafo de Petersen possui um \( K_5 \) como menor.

IV) O grafo de Petersen menos um vértice é uma subdivisão do \( K_{3,3} \).

a) Apenas as afirmações I , II e III  estão corretas.

b) Apenas as afirmações I,  III e IV estão corretas.

c) Apenas as afirmações I, II e IV estão corretas.

d) Todas as afirmações estão corretas.

e) N.D.A.

Ideia original de: G. Michel Carvalho

2024-168

 Considere as seguintes afirmações:

I-) Seja G* (figura baixo) o grafo dual de um grafo conexo G. Podemos afirmar que G é o grafo casa.

II-) Existe um grafo planar com 8 vértices, 10 arestas e 3 faces.

III-) Seja G um grafo planar com sequência de graus S = {2, 3, 3, 5, 5}. Podemos afirmar que G tem 6 faces.

IV-) Dados os grafos G1, G2 e G3 abaixo, podemos afirmar que apenas G1 é cordal.

Assinale a alternativa CORRETA:

a-) Apenas as afirmativas I e III são VERDADEIRAS

b-) Apenas as afirmativas II e IV são VERDADEIRAS

c-) Apenas as afirmativas III e IV são VERDADEIRAS

d-) Apenas as afirmativas I, III e IV são VERDADEIRAS

e-) N.D.A.

Ideia original de: Guilherme A. Terrell

2024-167

Considere os grafos \( H \) e \( H' \) abaixo:

e as afirmações:

I - Os grafos \(H\) e \( H' \) são planares;

II - O grafo \( H' \) é um grafo triangulado;

III - O grafo \( H \) é um grafo triangulado;

Quais das afirmações acima estão corretas?

a) apenas I;

b) apenas I e II;

c) apenas I e III;

d) apenas II e III;

e) NDA;

Ideia original de: Gabriel S. Kraszczuk 

2024-166

Definimos a função \( \nu_g(G) \) como sendo o menor número de cruzamentos de uma imersão de \( G \) em uma superfície de gênus \( g \).  Atribuindo valores 1, 2, 4 e 8 às seguintes afirmações:

(1) Para todo os inteiros \( g, h \geq 0 \) e para todos os grafos \( G \) , se \( g \leq h \) então \( \nu_g(G) \leq \nu_h(G) \),

(2) \( \nu_{1}(K_{3,3}) = 0 \),

(4) Para todo \( n \geq 1 \) e todo \( g \geq 0 \), temos que  \( \nu_{g}(K_{2,n}) = 0 \),

(8) \( \nu_{0}(K_5) = 1 \),

a soma das afirmações corretas é:

A) 3

B) 10

C) 12

D) 15

E) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian

2024-164

Considere um grafo \(G\) com 8 vértices e 12 arestas. O que podemos afirmar com certeza sobre \(G\)?

a) O grafo \(G\) é necessariamente um grafo planar.

b) O grafo \(G\) possui um ciclo hamiltoniano.

c) O grafo \(G\) é bipartido.

d) O grafo \(G\) contém um subgrafo isomórfico ao \( K_5 \)​.

e) N.D.A.

Ideia original de: Glaymar A. França 

2024-163

Considere o grafo abaixo:

Quais das afirmações a seguir não estão corretas?

I - O grafo acima é planar (pode ser desenhado no plano sem o cruzamento de arestas)

II - O número de faces do grafo acima, (em sua representação no plano sem cruzamento de arestas) é 6.

III - O número cromatíco do grafo acima é 3.

IV -  O número cromático do grafo acima é 4.

a) I e II;

b) apenas a II;

c) III e IV;

d) apenas a IV;

e) NDA;

Ideia original de: Gabriel S. Kraszczuk

2024-162

Considere as afirmações abaixo:

1) O grafo representado abaixo não é planar.

2) Considerando que um grafo plano \(G\) é legalzão se 1) \(G\) é ismorfo ao seu dual \(G^*\) e 2) é conexo. Então, todo grafo legalzão tem um número par de arestas.

4) O maior \(k\) natural que satisfaz a seguinte propriedade: "todo grafo simples com \(n(G) \leq k\) é planar" é um número quadrado perfeito.

8) Considere um grafo planar \(G\) com \( n(G)=10 \), \( e(G)=12 \). Então \(G\) tem exatamente 4 faces.

A soma das alternativas verdadeiras é:

A) 2

B) 6

C) 14

D)15

E) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian.