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-165

Sobre polinômios cromáticos, assinale a alternativa correta:

1. \( \chi(K_n, k) = k(k-1) \ldots (k - (n-1)) \);
   \( \chi(P_n, k) = k(k-1)^{n-1} \);
   \( \chi(C_n, k) = (k-1)^{n} + (-1)^n(k-1) \).
2. \( \chi(C_n, k) = k(k-1) \ldots (k - (n-1)) \);
   \( \chi(K_n, k) = k(k-1)^{n-1} \);
   \( \chi(P_n, k) = (k-1)^{n} + (-1)^n(k-1) \).
3. \( \chi(P_n, k) = k(k-1) \ldots (k - (n-1)) \);
   \( \chi(K_n, k) = k(k-1)^{n-1} \);
   \( \chi(C_n, k) = (k-1)^{n} + (-1)^n(k-1) \).
4. \( \chi(P_n, k) = k(k-1) \ldots (k - (n-1)) \);
   \( \chi(C_n, k) = k(k-1)^{n-1} \);
   \( \chi(K_n, k) = (k-1)^{n} + (-1)^n(k-1) \).
5. N.D.A.

Ideia original de: G. Michel Carvalho

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.

2024-161

Dado o grafo abaixo e considerando \(k\) cores, qual das alternativas a seguir exibe uma ordem de eliminação perfeita, anotada com o número de cores livres disponível para cada vértice, no algoritmo guloso para uma coloração própria?

A) 1: \(k\), 2: \(k-1\), 3: \(k-2\), 4: \(k-1\), 5: \(k-2\)

B) 1: \(k\), 2: \(k-1\), 3: \(k-1\), 5: \(k-2\), 4: \(k-3\)

C) 1: \(k\), 2: \(k-1\), 3: \(k-1\), 4: \(k-1\), 5: \(k-3\)

D) 1: \(k\), 2: \(k-1\), 3: \(k-2\), 5: \(k-3\), 4: \(k-4\)

E) N.D.A.

Ideia original de: Artur Silveira 

2024-160

Qual é o polinômio cromático do grafo \( C_5 \):

a) \( k(k - 1)(k - 2)(k -3) \)

b) \( k(k - 1)(k - 2)(k -3)(k - 4) \)

c) \( k(k - 1)^4 \)

d) \( k^5 \)

e) N.D.A.

Ideia original de: Wellington T. A. da Silva