2026-322

Given a graph where each node represents a student and two students are connected by a link if they have ever studied at the same school (not necessarily in the same class or year), which of the following statements is true?

a) A node with clustering coefficient equal to 1 implies that the student never changed schools.

b) A complete graph implies that there is just one school.

c) A student who never changed schools will have clustering coefficient equal to 1.

d) The number of connected components in the graph is necessarily equal to the number of schools.

e) None of the above.

Original idea by: Henrique Campos Padula

2026-321

Let \(G=(V,E)\) be a simple undirected graph, meaning that it has no self-loops (edges of the form \((v, v)\)) and no multiple edges between the same pair of vertices.

For such a graph we can define its degree sequence, as the sequence of its vertex degrees in nonincreasing order..

For example, the graph shown below has degree sequence

(3,1,1,1)

For each of the following statements, determine whether it is True (T) or False (F).

i) \( (2,2) \) is the degree sequence of several nonisomorphic graphs.
ii) \( (2,2,2) \) is the degree sequence of exactly one graph, up to isomorphism.
iii) \( (2,2,2,2,2,2) \) is the degree sequence of exactly one graph, up to isomorphism.

Alternatives

a) FTF
b) FTT
c) TFT
d) TTF
e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

2026-320

Figure 1(a) below shows a drawing of a network \(N\). Figures 1(b), 1(c), and 1(d) show the matrices \(A\), \(D\), and \(S\), respectively, and Figure 1(e) shows the vector \(k\). 

Regarding the figures above, consider the following six propositions:

1. For matrix \(A\), shown in Figure 1(b), entry \(a_{ij} = 1\) if and only if there is a link in network \(N\) connecting node \(i\) to node \(j\). Therefore, \(A\) is the adjacency matrix of network \(N\).
2. Matrix \(D\), shown in Figure 1(c), can be regarded as a matrix indicating second neighbors (nodes at distance two) of network \(N\), since entry \(d_{ij} \not= \infty\) if and only if nodes \(i\) and \(j\) are second neighbors.
3. Matrix \(D\), shown in Figure 1(c), can be regarded as a distance matrix of network \(N\), since if \(d_{ij} = \infty\) there is no path between nodes \(i\) and \(j\), and if \(d_{ij} \not= \infty\) then \(d_{ij}\) equals the length of a shortest path between nodes \(i\) and \(j\).
4. Matrix \(S\), shown in Figure 1(d), can be regarded as a matrix of second neighbors of network \(N\), since \(s_{ij} = 1\) if, and only if, nodes \(i\) and \(j\) are second neighbors.    
5. Vector \(k\) is the vector of the node degrees of network \(N\) and can be obtained multiplying matrix \(A\) by vector \( (1, 1, \ldots, 1) \)^T \) .  

Which alternative contains all the TRUE propositions?

(a) 1 and 3.

(b) 1, 2, and 3.

(c) 1, 2, and 5.

(d) 1, 3, 4, and 5.

(e) None of the above.

Original idea by: Joao Vianini

2026-319

Consider the four graphs below:

Which graph has the highest average clustering coefficient C, and what is its value?

A) Graph 1, with C = 0

B) Graph 4, with C = 0.47

C) Graph 2, with C = 0.50

D) Graph 3, with C = 0.10

E) None of the above

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

2026-318

Suppose a graph \(G\) has the following second power of the adjacency matrix:

$$ A^2 = \left( \begin{array}{cccc}1 & 0 & 1 & 1\\0 & 3 & 1 & 1\\1 & 1 & 2 & 1\\1 & 1 & 1 & 2 \end{array}\right) $$

Which one could be \(G\)?

a)

b)

c) 

d) 

e) None of the above

Original idea by: Leticia Marques

2026-317

 In an undirected network, suppose there are exactly 4 triangles and exactly 12 additional connected triplets, not belonging to triangles.  According to the definition of the global clustering coefficient, what is the value of ?

1. 1/2
2. 2/3
3. 3/4
4. 6/7
5. None of the above

Original idea by: Antonio De Cesare Del Nero

2026-316

Consider the following graph and the subsequent statements:

1. The graph is connected because the links (0, 1), (0, 2) and (0, 3) intersect with the links (4, 5), (4, 6) and (5, 6).

2. If we consider the components of this graph as projections of a bipartite graph, the parent bipartite graph could be:

3. The adjacency matrix of this graph can be rearranged and separated into two non-zero submatrices of size 4x4 and 3x3.

The correct statements are:

a) Just 3

b) 1 and 2

c) 1 and 3

d) 2 and 3

e) None of the above.

Original idea by: Rafael Brusiquesi Martins