Probability that graph with $6$ vertices and $5$ edges has a triangle.

Question

How to calcultate a probability that a graph with $6$ vertices and $5$ edges has a triangle?

So we have ${15\choose 5}=3003$ (labeled) graphs and ${6\choose 3} =20$ possible triangles.

Let $m_i$ be a number of graphs with $i$-th triangle. Then $m_i= {12\choose 2}= 66$ and $m_{i,j} = 1$ if $\Delta _i$ and $\Delta _j$ have one common side, else it is $0$. Notice that $m_{i,j} = 1$ is $9$ times for each $i$. So $$m= 20\cdot 66 - {20\cdot 9\over 2} = 1230$$

So $$P = {1230\over 3003} \approx 0.41 $$

Is this correct and how to calculate this probability in general if we have $n$ vertices and $\varepsilon$ edges?

Answer 1

For integers $n,e$ with $n \ge 1$ and $e\ge 0$, let $S=S(n,e)$ be the set of simple graphs on the labeled vertices $1,...,n$ having exactly $e$ edges.

• Let $E(n,e)$ be the expected number of triangles for a randomly chosen graph from $S$.

  Then we get $$E(n,e)={\large{\frac { \binom{n}{3}\binom{m-3}{e-3} } { \binom{m}{e} }}} $$ where $m=\large{\binom{n}{2}}$.

• Let $T(n,e)$ be the number of graphs in $S$ having at least one triangle.

  A few partial results: $$ T(n,3)= \frac { n(n-1)(n-2) } {6} \\[16pt] T(n,4)= \frac{ n(n-1)(n-2)(n-3)(n+2) } {12} \\[16pt] T(n,5)= \frac { n(n-1)(n-2)(n-3)(n^3+n^2-10n-28) } {48} \\[16pt] T(n,6)= \frac { n(n-1)(n-2)(n-3)(n^5-21n^3-56n^2+152n+620) } {288} \\[12pt] $$ More generally, fixing $e\ge 3$, it's not hard to show that $$T(n,e)=\sum_{k=j}^{2e-3}a_k{\small{\binom{n}{k}}}$$ where

  • $j$ is the least positive integer such that ${\large{\binom{j}{2}}} \ge e$.$\\[4pt]$
  • Each $a_k$ is the number of simple graphs on the labeled vertices $1,...,k$ having exactly $e$ edges, at least one triangle, and no isolated vertices.$\\[14pt]$
  Noting that each $a_k$ is a positive integer constant (depending on $e$ and $k$, but independent of $n$), it follows that for all $e\ge 3$, we have $T(n,e)=\Theta(n^{2e-3})$.

Answer 2

I made a simulation. First, I created the triangle graph then generate the 100,000 random graphs with n=6 vertices and m=5 edges using the Erdos-Renyi model, and find the distribution of triangles.

The probability $P=0.40660 \approx 0.41$.

As one can see only two events were in the simulation: a) the random graph does not have a triangle, b) the random graph has one triangle. But in theory the graph $G(V, E)$ where $n=|V|=6$, $m=|E|=5$ can have two triangles with one common edge:

The R code is below.

library(igraph)

triangle <- graph_from_literal( A--B, B--C, C--A)

ntrials <- 100000
ntriangles <- numeric(ntrials)

for (i in (1:ntrials)) {
    g      <- erdos.renyi.game(n=6, p.or.m=5, type="gnm", directed=FALSE)
    iso    <- subgraph_isomorphisms(triangle, g)      
    motifs <- lapply(iso, function (x) { get.edgelist(induced_subgraph(g, x)) })
      ntriangles[i]  <- length(unique(motifs))
}

hist(ntriangles, freq=TRUE, labels = TRUE, breaks=3, col="red", xlim=c(0,2),
main="Triangle's distribution", xlab="Triangles")

two_triangles <- graph_from_literal( A--B, B--C, C--A, A -- D, D -- B, E, F)
plot(two_triangles)

Answer 3

As you say, there are $20$ possible triangles. Having made a triangle, there are $12$ edges left, so each one accounts for ${12 \choose 2}=66$ graphs. The cases where there are two triangles have been counted twice. For those, you choose four vertices to be part of the triangles, then delete one of the six edges of the $K_4$, so there are ${6 \choose 4}\cdot 6=90$ graphs with two triangles. By inclusion-exclusion there are $66 \cdot 20-90=1230$ graphs with triangles, so there are ${15 \choose 5}-1230=1773$ graphs without triangles. The chance is then $\frac {1773}{3003} \approx 0.59$ that there is no triangle.

Answer 4

Let's start by counting the labeled triangle-free graphs on $6$ vertices and $5$ edges. Let's classify them according to the cycles they contain.

Case 1. No cycles. An acyclic graph with $6$ vertices and $5$ edges is a tree. By Cayley's theorem, the number of labeled trees on $6$ vertices is $$6^4=\boxed{1296}.$$

Otherwise, the graph must contain a cycle of length $4$ or $5$, since $3$-cycles are forbidden and we don't have enough edges for a $6$-cycle.

Case 2. Cycle of length $5$. The only possible unlabeled graph is $C_5+K_1$; the number of labelings is $$\binom61\cdot\frac{4!}2=\boxed{72}.$$

Case 3. Cycle of length $4$. Here there are two possible unlabeled graphs.

Case 3a. $C_4+K_2$. The number of labelings is $$\binom62\cdot\frac{3!}2=\boxed{45}.$$

Case 3b. The graph with degree sequence $3,2,2,2,1,0$ in which the vertex of degree $1$ is adjacent to the vertex with degree $3$. There are $6\cdot5\cdot4$ ways to label the vertices of degree $0$, $1$, and $3$, and then $3$ ways to label the vertex of degree $2$ which is not adjacent to the vertex of degree $3$, so the number of labelings is $$6\cdot5\cdot4\cdot3=\boxed{360}.$$

Thus the number of triangle-free graphs is $$1296+72+45+360=1773;$$ the number of graphs with triangles is $$\binom{15}5-1773=3003-1773=1230;$$ so the probability that a random graph with $6$ vertices and $5$ edges will contain a triangle is $$\frac{1230}{3003}=\boxed{\frac{410}{1001}}\approx0.4096$$

which is the same answer you got.