Counting False-Twin Witnesses in Induced Subgraphs: An Exact Identity, a Two-Constraint Entropy Rate, and a Plateau

Given a fixed non-adjacent pair of vertices, suppose we know how many induced subgraphs make the pair look like false twins, allowing up to a prescribed number of disagreements. Can this local witness count recover how strongly the two vertices agree in the full graph? We study this inverse question. In the main deterministic setting, the graph size, the induced-subgraph size, the allowed number of disagreements and the exhaustive witness count are treated as known, while the global adjacency-agreement count is unknown. We first prove an exact counting formula and use it to determine when the unknown agreement count can be recovered uniquely and when saturation causes information to be lost. We then study the regime in which the subgraph size and the allowed number of disagreements grow proportionally with the graph. A method-of-types argument gives the exponential growth rate up to an O(logN) error. The resulting rate develops a plateau before the exact finite count itself becomes constant. Thus there is a range in which different global agreement levels are still distinguishable at finite size but are no longer distinguishable at exponential scale. In the exact-witness case we also obtain sharp asymptotic and finite-size stability estimates. Numerical calculations illustrate the finite-size behavior, and strongly regular graphs and the dense stochastic block model are discussed as examples.