3.1 Graph

Graph

A graph is a mathematical structure consisting of a set of vertices (nodes) $V$, and a set of edges $E\subseteq V\times V$, using which the vertices are connected together in some way. Graphs can be

• Directed graphs, used to model one-way relationships between vertices by arrows. The set $E$ of a directed graph is a set of pairs.
• Undirected graphs, modeling relationships of vertices that go both ways. The set $E$ of an undirected graph is a set of unordered sets.

The degree of a vertex (denoted $\mathrm{deg}v$) is the number of edges connected to it. In directed graphs, each vertex has an in-degree, and an out-degree.

Furthermore, we say that an edge $e=\{u,v\}$ is incident on vertices $\{u,v\}$, and that the vertices $u$ and $v$ are adjacent.

Properties

(Handshaking Lemma) In an undirected graph, ${\sum }_{v\in V}^{}\mathrm{deg}v=2|E|$.

This lemma is intuitive, since in an undirected graph each edge adds 1 to the degree of both endpoints. For a formal proof, we proceed by induction:

• Base Case: The lemma is true for a graph with zero edges (i.e., $|E|=0$).
• Hypothesis: Assume the lemma is true for all graphs with $\le k-1$ edges.
• Step: We want to prove for a graph with $k$ edges. We remove 1 edge, and the degrees of both affected edges is decreased by 1.

(Edge Bounds for Connected Undirected Graphs) A connected, undirected graph can consist of between $e\in \left[v-1,\frac{v(v-1)}{2}\right]$ edges.

We will see later that a connected undirected graph with $v-1$ edges is known as acyclic, or a tree. Although we can prove this, there is no need to. Same for the maximum.

Example

A Simple Example

Observe the following graph.

\begin{document}
\begin{tikzpicture}
 % Nodes
 \node (A) at (0, 2) [circle, draw] {A};
 \node (B) at (2, 3) [circle, draw] {B};
 \node (C) at (4, 2) [circle, draw] {C};
 \node (D) at (6, 3) [circle, draw] {D};
 \node (E) at (8, 2) [circle, draw] {E};
 \node (F) at (8, 0) [circle, draw] {F};
 \node (G) at (6, -1) [circle, draw] {G};
 \node (H) at (4, 0) [circle, draw] {H};
 \node (I) at (2, 0) [circle, draw] {I};
 \node (J) at (0, 0) [circle, draw] {J};
 \node (K) at (4, -2) [circle, draw] {K};
 \node (L) at (-2, 1) [circle, draw] {L};

% Edges
\draw (A) — (B);
\draw (A) — (J);
\draw (A) — (L);
\draw (B) — (C);
\draw (B) — (D);
\draw (C) — (D);
\draw (C) — (H);
\draw (D) — (E);
\draw (D) — (F);
\draw (E) — (F);
\draw (F) — (G);
\draw (G) — (H);
\draw (G) — (I);
\draw (H) — (I);
\draw (H) — (K);
\draw (I) — (J);

\draw (J) — (K);

% Special vertex connected to only one vertex

\draw (L) — (A);

\end{tikzpicture}

\end{document}

>[!example]- How many vertices and edges does the graph contain?
>The graph has 12 nodes (vertices) and 17 edges.

Degree Sequences

The degree sequence of a graph is the sequence of the degrees of the vertices, arranged in descending order. For each of the parts below, determine if there exists a simple undirected graph $G$ having the given degree sequence. Justify your claim.

$(3,3,2,2)$ This is a possible degree sequence of a graph with 4 vertices. For an example, consider a square with only one of its diagonals as an edge.

$(3,2,2,2,2,1,1)$ This graph has 7 vertices. If we group the actual degree sequence for a graph with an odd number of vertices,

Build-Up Error