# Count chains in complete graph

Let's say I have a complete graph like this

W = {1, 2};
n = 5;
p2 = 0.5;
p1 = 1 - p2;
arr = {};
AppendTo[arr, RandomChoice[{p1, p2} -> {1, 2}, n]];
el1 = VertexList[CompleteGraph[n]];
g = CompleteGraph[n,
VertexLabels -> Table[el1[[i]] -> arr[[1]][[i]], {i, Length[el1]}],
VertexSize -> .10]
SeedRandom[1];
chain = {1,2,2};


There are 6 possible chains {1,2,2} for this particular graph

I need to write a function that receives a complete graph g and a chain chain(1 < Length[chain] < n) and returns a number of such chains in g.

• Look up "graph coloring"... a very well-developed field which uses colors instead of the labels 1 and 2. Commented May 30, 2023 at 22:27
• Can you clarify, ideally through a concrete example, what you mean by "the number of required chains", or even what you mean by "chain" in this context? Commented May 31, 2023 at 9:59
• is it always the case that Length[chain] <= VertexCount[g]?
– kglr
Commented May 31, 2023 at 14:48
• Yes, it is like that 1 < Length[chain] < n Commented May 31, 2023 at 14:56

\$Version

"13.1.0 for Linux x86 (64-bit) (June 16, 2022)"

ClearAll[chainCount]

chainCount[g_, p_] /; SubsetQ[Values@AnnotationValue[g, VertexLabels], p] :=
Module[{cp = Counts @ p,
cg = Counts @ Values @ AnnotationValue[g, VertexLabels]},
Apply[Times] @
MapApply[FactorialPower] @
Select[Length @ # == 2 &] @ Merge[Identity] @ {cg, cp}]

chainCount[g_, p_] = 0;


Examples:

n = 5;
p = 0.5;
SeedRandom[1];
arr = RandomChoice[{1 - p, p} -> {1, 2}, n];

g = CompleteGraph[n, VertexLabels -> {v_ :> arr[[v]]}, VertexSize -> .10]

chainCount[g, {1, 2, 2}]

6

chainCount[g, {1, 1, 2}]

12

chainCount[g, {2, 2, 2}]

0

chainCount[g, {1, 1, 1}]

6

chainCount[g, {1, 2, 1, 1}]
12

• Maybe I am missing something but, for example, chainCount[g, {1, 2, 2}] returns <|2 -> {2, 2}, 1 -> {3, 1}|> Commented May 31, 2023 at 16:05
• @mclord, could be version/os difference (I am using v13.0 for linux x86). Try also starting with a fresh kernel.
– kglr
Commented May 31, 2023 at 16:26