Graph properties

Overview

Some questions are about a graph's local structure. Counting triangles — triples of mutually adjacent vertices — is a disciplined i<j<k scan so each triangle is counted exactly once. A universal sink is the graph 'celebrity': a vertex everyone points to that points to no one, i.e. an all-zero matrix row with an all-one column off the diagonal.

Why it matters

Triangle counts measure clustering in social and biological networks (the clustering coefficient). The universal-sink / celebrity problem is a classic interview and systems question — finding a single node that everyone depends on but that depends on nothing.

Core concepts

Triangles via i<j<k. Requiring strictly increasing indices counts each triangle once instead of six times.

Universal sink. Vertex v qualifies iff row v is all zeros (out-degree 0) and column v is all ones except the diagonal (everyone else points to v).

Matrix reading. Both properties are pure, careful reads of the adjacency matrix — good practice for row/column reasoning.

Why the sink test needs both halves. An all-zero row alone identifies a vertex that points at nothing, which could simply be isolated; an all-one column alone identifies a popular vertex that may still point elsewhere. Only together do they describe a vertex the whole graph depends on and which depends on nothing.

Syntax notes

/* count triangles in an UNDIRECTED graph: i < j < k counts each once */
int count_triangles(const int *adj, int n) {
    int c = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (adj[i*n + j])                       /* prune: no edge i-j, skip all k */
                for (int k = j+1; k < n; k++)
                    if (adj[j*n + k] && adj[i*n + k]) c++;
    return c;
}

/* a universal sink: out-degree 0, and every OTHER vertex points to it */
int has_universal_sink(const int *adj, int n) {
    for (int v = 0; v < n; v++) {
        int out = 0;
        for (int j = 0; j < n; j++) out += adj[v*n + j];
        if (out != 0) continue;                     /* row must be all zeros */
        int ok = 1;
        for (int i = 0; i < n && ok; i++)
            if (i != v && !adj[i*n + v]) ok = 0;    /* column all ones except the diagonal */
        if (ok) return 1;
    }
    return 0;
}

Key points:

• i < j < k is what counts each triangle exactly once instead of six times.
• Testing adj[i][j] before the innermost loop is a real prune, not just style.
• A sink needs both conditions: empty row and full column (excluding the diagonal).

Lesson

Many graph questions are structural. Counting triangles (mutually adjacent triples) is a disciplined i<j<k scan so each is counted once. A universal sink — the 'celebrity' with out-degree 0 that everyone points to — is a vertex whose matrix row is all zeros and whose column is all ones off the diagonal. Both are clean exercises in reading an adjacency matrix carefully.

Code examples

#include <stdio.h> int main(void){ int n=4; /* K4 minus one edge / int adj[16]={ 0,1,1,1, 1,0,1,1, 1,1,0,0, 1,1,0,0 }; int tri=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(adj[in+j]) for(int k=j+1;k<n;k++) if(adj[jn+k]&&adj[in+k]) tri++; printf("triangles = %d\n", tri); int sink=-1; for(int v=0;v<n;v++){ int out=0,into=0; for(int j=0;j<n;j++) out+=adj[vn+j]; for(int i=0;i<n;i++) if(i!=v) into+=adj[in+v]; if(out==0&&into==n-1) sink=v; } printf("universal sink = %d\n", sink); return 0; }

Line by line

Common mistakes

Counting ordered triples and over-counting triangles by 6×. Forgetting a sink must have no outgoing edges as well as all incoming ones. Off-by-one at the diagonal (a vertex need not point to itself).

Debugging tips

Compiler errors and warnings:

• -Wsign-compare on loop bounds; keep indices int.
• Nothing warns about counting triples in the wrong order.

Runtime symptoms:

• Triangle count is 6x too high. You looped all three indices independently instead of enforcing i < j < k.
• Triangle count is 2x too high. You enforced i < j but not j < k.
• Zero triangles in an obviously triangular graph. The matrix is not symmetric — this counts undirected triangles and assumes symmetry.
• A sink is reported that has outgoing edges. You checked only the column, not the row. Both conditions are required.
• No sink found in a graph that clearly has one. You required adj[v][v] to be set; the diagonal must be excluded with i != v.
• Slow on large graphs. Triangle counting is O(n^3); that is inherent to this brute-force form.

Technique: test K4 (4 triangles), a square with no diagonals (0), and a 3-vertex graph where vertex 2 is a sink. Those three cover both algorithms and the common miscounts.

Memory safety

• No allocation at all — both functions are pure reads of the caller's matrix, so there is nothing to leak or free. The risks are purely in index discipline.
• Index bounds. Every access is adj[x*n + y] with x, y strictly less than n; the loop bounds guarantee that, so do not "optimise" them into forms that could exceed n-1.
• Symmetry precondition. Triangle counting assumes an undirected (symmetric) matrix; the sink test assumes a directed one. Running either on the wrong kind of graph gives a silently wrong answer with no crash.
• Self-loops. The sink test deliberately skips the diagonal. If your convention allows adj[v][v] = 1, the row-sum test would then reject a valid sink — decide the convention and apply it consistently.
• Complexity as a resource limit. O(n^3) on an untrusted n is a denial-of-service risk; bound the input size.

Real-world uses

Concrete uses: Triangle counts measure clustering in social and biological networks — the local clustering coefficient is built directly from them — and are used in spam and fraud detection, where unusually dense triangles signal collusion. The universal-sink ("celebrity") problem models finding a single node everyone depends on but which depends on nothing: a root package, a central authority, or a terminal state. It is also a classic interview question because a smarter O(n) algorithm exists.

Professional best practices:

Beginner:

• Enforce i < j < k rather than counting and dividing.
• Check both the row and the column for a sink.

Intermediate:

• For large sparse graphs, count triangles by iterating adjacency lists and intersecting neighbourhoods rather than the O(n^3) triple loop.
• The sink problem has an elegant O(n) solution: walk from a candidate, discarding one vertex per comparison, then verify the survivor once. Implement it once — it teaches the value of a verification pass.
• State the directed/undirected expectation in the function's documentation, since neither can detect a violation.

Practice tasks

1. (Beginner) Count triangles. Implement int count_triangles(const int *adj, int n) with i < j < k. Example: K4 -> 4; a square without diagonals -> 0. Concepts: counting each triple once.

2. (Beginner) Universal sink. Implement int has_universal_sink(const int *adj, int n) checking both the row and the column. Concepts: the two required conditions.

3. (Intermediate) Show the miscount. Loop all three indices independently and confirm the triangle count comes out 6x too high. Concepts: why ordering the indices matters.

4. (Intermediate) O(n) sink. Implement the linear celebrity algorithm — eliminate one candidate per comparison, then verify the survivor. Concepts: candidate elimination plus a verification pass.

Summary

Both properties are careful reads of the adjacency matrix. Counting triangles with strictly increasing indices i < j < k generates each unordered triple exactly once — no dividing by six — and testing edge i-j before entering the innermost loop is a genuine prune. A universal sink is the graph's "celebrity": out-degree 0, so its row is all zeros, while every other vertex points to it, so its column is all ones except the diagonal — and requiring only one of those two conditions is the usual bug. Neither function allocates, so the risks are entirely about index discipline and about the unchecked directed-versus-undirected precondition; note also that the O(n^3) triangle scan needs an input bound on untrusted data.

Practice with these exercises

• Count triangles
• Universal sink