= Simple graph
An undirected simple <graph> is exactly a pair of <sets>
$$
G=(V,E),\qquad E\subseteq\{\{u,v\}:u,v\in V,\ u\ne v\}.
$$
Thus every <edge> is a two-element <set> of distinct <vertices>. The <unordered pair> $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes <self-loops>, and using a <set> of <edges> excludes parallel copies. A <simple graph> may have <vertices> with no incident <edges>; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same <edge> <set> but different <vertex sets>.https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec11.pdf[MIT, Graphs and Coloring, Section 1.1]{ref}
In the six-<vertex> example, the <vertex neighbourhood> of $C$ is $\Gamma(C)=\{A,B,D\}$, so its <degree of a vertex> is $\deg(C)=3$. In label order $A,B,C,D,E,F$, the <degree sequence> is
$$
(2,2,3,3,2,2),\qquad \sum_{v\in V}\deg(v)=14=2\cdot7=2|E|.
$$
This is the <handshaking lemma>: count each <edge> once at each of its two endpoints. The <average degree of a graph> here is $14/6=7/3$. The <degree sequence> is a compact consistency check on an <edge> list; an odd sum could not describe any finite undirected <graph>. It also forces the number of odd <degrees of vertices> to be even, since the even terms do not affect the parity of the sum.
The <adjacency matrix> in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a <symmetric matrix> with zero diagonal, and each row sum gives the corresponding <vertex degree>. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected <edges>; they do not indicate fourteen different <edges>. This translates a picture into a representation suitable for calculation.
The restrictions matter. A <directed graph> uses an <ordered pair> to distinguish $u\to v$ from $v\to u$, so <reachability> can depend on direction. A <multigraph> can contain several distinct <edges> between the same <vertices>; adding another $CD$ would raise $\deg(C)$ and $\deg(D)$ to four without adding a new neighbour. A <self-loop> at $A$ contributes two to its undirected <vertex degree>, making it four, because both endpoints lie at $A$. Specify whether <self-loops> are allowed in a <multigraph>. Finally, a <weighted graph> attaches numerical information to <edges>: if links carry travel times, minimizing the number of <edges> need not minimize total time. These are changes to the model, rather than changes to how the same <simple graph> is drawn.
Back to article page
