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