---- > [!definition] Definition. ([[mean degree]]) > The **mean degree** $c$ of a node in an [[network|undirected network]] is the arithmetic mean $c:=\frac{1}{n}\sum_{i=1}^{n}k_{i}=\frac{2m}{n},$ > where $n$ denotes the number of nodes in the [[network]] and $m$ the number of edges. > [!basicexample] > > [!proposition] Proposition. > The **mean degree** of a [[simple graph|simple]], [[connected graph|connected]], [[planar graph]] is strictly less than $6$. > \ > So, for example, the average number roads that meet at an intersection is strictly less than $6$. > > > [!proof] Proof of Proposition. > > Let $G$ be [[simple graph|simple]]; we'll show $\frac{2m}{n} < 6$. Let $f$ denote the number of [[graph face|faces]] of $G$. Since each [[graph face|face]] is enclosed by at least $3$ edges, it is tempting to claim that $\textcolor{Apricot}{3f \leq m}$. However, one edge can correspond to multiple faces— so this would in general overcount. Thus, we ask: by *how much* does it overcount? Well, each edge straddles at most $2$ faces. Therefore, $(\text{edges per face})\textcolor{LimeGreen}{ \ \ \ 3f \leq 2m} \ \ \ \text{(faces per edge)}$ > > is the correct inequality. > > Now we substitute $f=2-n+m$ using [[Euler's graph formula]] to obtain $\begin{align} 2m \geq 3(2-n+m) \iff & 2m \leq 6-3n+3m \\ \iff & \textcolor{Thistle}{\left( \frac{2}{n} \right)}3n-6 \geq m \textcolor{Thistle}{\left( \frac{2}{n} \right)} \\ \iff & 6-\frac{6}{n} \geq \frac{2m}{n} \\ \iff & 6 \geq \frac{2m}{n}+\frac{6}{n} \\ \iff & 6 > \frac{2m}{n}. \end{align}$ > ---- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```