2026-353

When analyzing the resilience of complex systems, network science literature establishes a fundamental distinction between static structural robustness and dynamic robustness

Consider Watts' Linear Threshold Model, where a network initialized with all functional nodes undergoes a local shock. In this model, a healthy node \(i\) transitions to a failed state if the fraction \(f_i\) of its inoperable neighbors exceeds a local critical threshold \(\phi\).

Based on the theoretical pillars of Network Robustness and the phase diagrams of this model, select the alternative that correctly describes the relationship between network topology, stability limits, and the propagation of catastrophic cascades:

A) In Watts' cascade model, the occurrence of a global avalanche exhibits a non-monotonic dependence on the network's average connectivity \(\langle k \rangle\). In highly dense networks (high \(\langle k \rangle\)), the system enters a subcritical regime where the failure of a single neighboring node represents a perturbation fraction \(1/k\) that is strictly lower than the critical threshold \(\phi\), thereby locally confining the impact and preventing global cascade propagation.

B) Scale-free networks with a degree exponent \(2 < \gamma \leq 3\) are ultra-robust against random structural failures (\(f_c\) → 1) due to the topological protection provided by hubs. This property automatically guarantees absolute immunity against global dynamic cascades triggered by minor shocks in peripheral nodes, since hubs invariably act as static sinks that absorb the overload and halt the domino effect.

C) The Molloy-Reed criterion (\(\kappa = \langle k^2 \rangle/\langle k \rangle > 2\)), which dictates the existence of a giant connected component in networks under inverse percolation, perfectly defines the dynamic threshold for avalanches. This explains why networks violating this inequality become inherently immune to cascading failures in the branching model, keeping the critical avalanche exponent unaltered.

D) According to the modeling of cascades via branching processes, the exponent α of the avalanche size distribution (\(P(S) \sim S^{-\alpha}\)) is a universal constant fixed at \(\alpha = 3/2\) for any complex network configuration, regardless of the underlying shape of the system's original degree distribution \(p_k\).

 E) None of the above.

Original idea by: Maria Luiza Ramos da Silva 

2026-352

Considering a scale-free network with a degree distribution \(P(k) \sim k^{-\gamma}\) and its critical threshold given by

$$f_c = 1 - \frac{1}{\frac{\langle k^2\rangle}{\langle k\rangle} - 1},$$

select the correct alternative.

1. For \(2 < \gamma < 3\), the second moment of the degree distribution tends to zero, indicating extreme fragility to random failures.
2. For \(\gamma > 3\), the second moment of the degree distribution diverges, making the network completely robust.
3. The value of \(f_c\) is independent of the exponent, depending only on the network size \(N\).
4. For \(2 < \gamma < 3\), the second moment of the degree distribution diverges and \(f_c\) tends to 1, indicating that the network can sustain the random removal of almost all nodes without losing the giant component.
5. None of the above

Original idea by: Julia de Pietro Bigi

2026-351

 Consider the network below:

What is the Pearson degree correlation coefficient (r) for this network using Mark Newman's definition?

A. r = 0, since the average degree of every node’s neighbors equals ⟨k⟩.

B. r = -2/3, indicating the network is assortative.

C. r = +2/3, indicating the network is disassortative.

D. r = -1/2, indicating the network is assortative.

E. None of the above.

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

2026-350

Epidemiologists are studying the spreading of a disease through an interaction network. After collecting data, they find that the network's degree distribution follows a power law \(p_k \sim k^{-\gamma}\) with exponent \(gamma = 2.5\), suggesting that a small number of highly connected individuals ("superspreaders") play a dominant role in transmission. The network has a minimum degree \( k_{min} = 2\), meaning every user follows at least two others, and an average degree \( \langle k \rangle = 8\). Structural analysis reveals a cutoff \(k_s = 64\), beyond which the simple-graph constraint begins to limit how hubs can connect to one another. Based on this information, which of the following alternatives is correct?

1. \(k_{max} = 128\), and the network presents structural assortativity because \(k_s < k_{max}\).
2. \(k_{max} = 64\), and the network does not present structural disassortativity because \(\gamma > 2\).
3. \(k_{max} = 128\), and the network presents structural disassortativity because \(k_s < k_{max}\).
4. \(k_{max} = 64\), and the network does not present structural disassortativity because \(k_s \geq k_{max}\).
5. None of the above

Original idea by: Carlos Trindade

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