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