Fracture Ray

Removing an edge set $F$ disconnects the graph if and only if $F$ contains a nonempty cut. Since $|F|=3$, only cuts of sizes $1$, $2$, and $3$ matter.

Cut fingerprints. Fix a DFS spanning tree. Give every non-tree edge an independent random 128-bit value and XOR that value at both endpoints. Accumulating the vertex values in postorder assigns a value $h(e)$ to every tree edge as well.

The XOR of $h(e)$ over every cut is always zero. For a fixed edge set that is not a cut, the probability that its XOR is accidentally zero is at most $2^{-128}$. Therefore, deleting three edges $e_1,e_2,e_3$ disconnects the graph exactly when one of the following tests succeeds, except with the stated negligible error probability:

• Some $h(e_i)$ is zero.
• Two fingerprints are equal.
• $h(e_1)\mathbin{\mathrm{xor}}h(e_2)\mathbin{\mathrm{xor}}h(e_3)=0$.

A connected simple graph with three edges is a star, a length-three path, or a triangle.

Stars. Fix the center $v$. The edges from $v$ into each connected component of $G-v$ form one group. Removing three incident edges disconnects the graph exactly when the chosen edges contain one complete group.

Let $a,b,c$ be the numbers of groups of sizes $1,2,3$, respectively, and let $d$ be the degree of $v$. The number of valid stars centered at $v$ is

$$\binom d3-\binom{d-a}3+b(d-a-2)+c.$$

DFS low-link values identify the separated child subtrees. For every non-tree edge, binary lifting finds the first child below its ancestor endpoint, which allows all group sizes to be computed in $O(M\log N)$ time.

Paths and triangles. Fix an edge $uv$ as the middle edge. Choose another edge incident to $u$ and another edge incident to $v$. Every length-three path is counted once, while every triangle is counted three times.

Let the middle fingerprint be $b$ and the outer fingerprints be $x,y$. If $x$ or $y$ equals $0$ or $b$, the cut condition already holds. Otherwise, only and are valid. Maintain fingerprint frequencies at every vertex and iterate over the endpoint of smaller degree. High-degree vertices use hash tables; low-degree vertices use binary search in sorted arrays. The sum of the smaller endpoint degrees over all edges is .

Enumerate triangles in $O(M\sqrt M)$ by orienting edges according to degree. Let $Q$ be the number of triangles satisfying the cut test. Since the middle-edge method counts each such triangle three times, the final answer is

$$(\text{number of stars})+(\text{middle-edge count})-2Q.$$

The time complexity is $O((N+M)\log N+M\sqrt M\log M)$ and the space complexity is . Frequency queries at high-degree vertices use expected constant time. The false-positive probability for each fixed non-cut is at most . For small , enumerate all connected triples and use distinct basis vectors for non-tree edges to obtain exact cut fingerprints. With maximum degree , enumerating stars and the two outer edges around each middle edge takes time. The general algorithm above also handles the remaining subtasks.

Solution written by GPT6