2026-349

Prof. John was playing an RPG game with his students. He then shows this dice to them and says that it is a dodecahedron and we can represent its vertices and edges as a graph:

Four students come up with different observations about the dice:

Student 1 says: The planar representation of the dice graph is

Student 2 says: The graph represented by the vertices and edges of the dice is three-dimensional, therefore, not planar.

Student 3 says: The standard Euler formula only applies to planar graphs, needing to be adjusted into \(N - L + F = 1 \) to account for the topological change in regular polyhedra like this dice.

Student 4 says: The planar representation of the dice graph is

Which student is right?

A) Student 1.

B) Student 2.

C) Student 3.

D) Student 4.

E) None of the above.

Original idea by: Rafael Brusiquesi Martins

2026-348

You’ve been in the hospital waiting room for a long time. After staring at the artwork for so long, you begin to notice that the drawings in the frames look a lot like graphs. To pass the time, you decide to figure out which graphs are planar and which are not. The figure below illustrates how you see the artwork on the hospital wall.

Select the option below that contains only frames whose drawings represent planar graphs:

A) Only Frame 1;

B) Only Frame 3;

C) Frame 1 and Frame 2;

D) Frame 1, Frame 2, and Frame 3;

E) None of the above.

Original idea by: Melissa Araújo.

2026-347

Evaluate the following statements regarding planarity and planarity testing algorithms:

I. A multi-graph is considered planar when it admits a plane drawing where links meet only at extremities.

II. To prove Euler's formula, one can start with a single node and observe the effect on the number of nodes, links, and faces when adding a new node connected to an existing node, and when adding a link between two existing nodes in the same face.

III. Kuratowski's Theorem states that a graph is planar if and only if it contains a subdivision (the process of replacing a link by a path) of, effectively making them mandatory subgraphs for planarity.

IV. The pseudo-code for the DMP algorithm begins by starting with a single node and iteratively selects a fragment with the maximum number of faces that contain all its vertices of attachment

V. When using the DMP algorithm, a fragment of a graph \(G\) with respect to a subgraph \(H\) can be an edge in \(G\) that is not in \(H\) but whose endpoints are located in \(H\)

Choose the alternative that correctly identifies the true statements:

a) Only statements I, III, and IV are true. 

b) Only statements II, III, and V are true. 

c) Only statements I, II, and V are true. 

d) All statements are true. 

e) None of the above.

Original idea by: Matheus de Oliveira Saldanha

2026-346

Consider a "Feasibility Matrix" \(M\) for all \(n, m \geq 1\), where an entry \(M_{n,m}\) is equal to 1 if a planar layout for the graph \(K_{n,m}\) is possible, and equal to 0 otherwise. Which of the following statements is true?

a) \(M_{n,m} = 0\) for all cases where \(n + m > 5\).

b) \(M_{2,m} = 1\) for all \(m \geq 1\).

c) The graph \(K_{3,3}\) is planar because it is possible to draw it in a 2D plane without any edges intersecting.

d) Every graph \(K_{n,m}\) is planar as long as \(n \neq m\).

e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

2026-345

The administration of a major university plans to create paths connecting all restaurants in one of its campuses, to optimize pedestrian mobility. Due to environmental restrictions, tunnels are forbidden, and no path can cross another path. Considering the campus map below, where the red dots represent restaurants, choose the correct alternative:

a) The project would be feasible if the restaurants were divided into 2 groups of 4, with only one path connecting the groups.

b) The project would only be feasible if two of the restaurants were not directly connected to the others.

c) The project is feasible, since it is possible to create paths connecting all 8 restaurants pairwise, without crossing.

d) There is no way that the project would be feasible.

e) None of the above.

Original idea by: Ingrid Barbosa

2026-344

In a Barabási-Albert model with m = 2, node A is added at time tA= 1 and node B at time tB = 4, as illustrated in the Figure. Here tA and tB are the birth times ti of each node. What is the ratio kA(100) / kB(100)?

1. 1/2
2. 1
3. 4
4. 10
5. None of the above

Original idea by: Gustavo P. C. P. da Luz

2026-343

Consider a network that follows the Barabási-Albert model with \(m_0 = m = 2\). A node \(i\) joined the network at time \(t_i = 375\) and has degree \(k_i(t) = 40\) at the current time step. What is the expected diameter of this network now? Round to two decimal places.

1. \(\langle D \rangle \approx 4.20\)
2. \(\langle D \rangle \approx 4.81\)
3. \(\langle D \rangle \approx 2.80\)
4. \(\langle D \rangle \approx 3.81\)
5. None of the above

Original idea by: Carlos Trindade