miniliv4
2022-10-02
Answered

Why a complete graph has $\frac{n(n-1)}{2}$ edges?

You can still ask an expert for help

falwsay

Answered 2022-10-03
Author has **8** answers

A simpler answer without binomials: A complete graph means that every vertex is connected with every other vertex. If you take one vertex of your graph, you therefore have $n-1$ outgoing edges from that particular vertex.

Now, you have $n$ vertices in total, so you might be tempted to say that there are $n(n-1)$ edges in total, $n-1$ for every vertex in your graph. But this method counts every edge twice, because every edge going out from one vertex is an edge going into another vertex. Hence, you have to divide your result by $$2$$. This leaves you with $n(n-1)/2$.

Now, you have $n$ vertices in total, so you might be tempted to say that there are $n(n-1)$ edges in total, $n-1$ for every vertex in your graph. But this method counts every edge twice, because every edge going out from one vertex is an edge going into another vertex. Hence, you have to divide your result by $$2$$. This leaves you with $n(n-1)/2$.

pokvarilaap

Answered 2022-10-04
Author has **3** answers

A complete graph has an edge between any two vertices. You can get an edge by picking any two vertices.

So if there are $n$ vertices, there are 𝑛 choose $$2=$$$(}\genfrac{}{}{0ex}{}{n}{2}{\textstyle )}=n(n-1)/2$ edges.

So if there are $n$ vertices, there are 𝑛 choose $$2=$$$(}\genfrac{}{}{0ex}{}{n}{2}{\textstyle )}=n(n-1)/2$ edges.

asked 2021-09-08

A restaurant offers a $12 dinner special with seven appetizer options, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?

asked 2021-09-09

In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?

asked 2021-08-19

What does it mean for an event to be unusual? Why should the cutoff for identifying unusual events not always be 0.05?

asked 2020-12-05

A sports team has 7 players. In how many ways can the team select a captain and junior captain?

asked 2022-06-04

Let us suppose to have a set of $N$ elements and to choose $m$ elements out of the set. I know I can do it in $(}\genfrac{}{}{0ex}{}{N}{m}{\textstyle )$ ways; but I want to know how many of these combinations contain $k$ predefined elements (say $1,2,...,k$).

asked 2022-05-21

Suppose that I am buying cakes for a party. There are $k$ different types and I intend to buy a total of $n$ cakes. How many different combinations of cakes could I possibly bring to the party?

asked 2022-11-20

Show without using the preceding results * that the probability ${p}_{m}(r,n)={n}^{-1}{E}_{m}(r,n)$ of finding exactly 𝑚 cells empty satisfies

${p}_{m}(r+1,n)={p}_{m}(r,n)\frac{n-m}{n}+{p}_{m+1}(r,n)\frac{m+1}{n}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}(1)$

* The results which I can't use must be

${E}_{m}(r,n)={\textstyle (}\genfrac{}{}{0ex}{}{n}{m}{\textstyle )}A(r,n-m)={\textstyle (}\genfrac{}{}{0ex}{}{n}{m}{\textstyle )}\sum _{\nu =0}^{n-m}(-1{)}^{\nu}{\textstyle (}\genfrac{}{}{0ex}{}{n-m}{\nu}{\textstyle )}(n-m-\nu {)}^{r}$

and by association

$A(r,n+1)=\sum _{k=1}^{r}{\textstyle (}\genfrac{}{}{0ex}{}{r}{k}{\textstyle )}A(r-k,n)$

By the way, $A(r,n)$ is equal to $n!S(r,n)$ where $S(r,n)$ are the Stirling numbers of the second kind.

${p}_{m}(r+1,n)={p}_{m}(r,n)\frac{n-m}{n}+{p}_{m+1}(r,n)\frac{m+1}{n}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}(1)$

* The results which I can't use must be

${E}_{m}(r,n)={\textstyle (}\genfrac{}{}{0ex}{}{n}{m}{\textstyle )}A(r,n-m)={\textstyle (}\genfrac{}{}{0ex}{}{n}{m}{\textstyle )}\sum _{\nu =0}^{n-m}(-1{)}^{\nu}{\textstyle (}\genfrac{}{}{0ex}{}{n-m}{\nu}{\textstyle )}(n-m-\nu {)}^{r}$

and by association

$A(r,n+1)=\sum _{k=1}^{r}{\textstyle (}\genfrac{}{}{0ex}{}{r}{k}{\textstyle )}A(r-k,n)$

By the way, $A(r,n)$ is equal to $n!S(r,n)$ where $S(r,n)$ are the Stirling numbers of the second kind.