(also called a *simple undirected graph* in the mathematical literature) $G$ is a pair consisting of a set $V$ called the set of vertices of $G$ and a set $E$ called the set of edges of $G$, whose elements are pairs of distinct elements of $V$. If $\{v,w\}$ is an edge, the vertices $v$ and $w$ are called *adjacent* or *neighbors*. They are the extremities of the edge $\{v,w\}$. Note that there is at most one edge between two vertices, and that there is no edge connecting a vertex with itself: the word *simple* above refers to these two restrictions.

**Adjacency matrix**: The adjacency matrix of a graph $G$ is a square matrix $M_{v,w}$ indexed by vertices of $G$ and such that $M_{v,w}=1$ if $\{v,w\}$ is an edge of $G$ and $0$ otherwise. Note that $M$ is a symmetric $0-1$ matrix with zeroes on the diagonal. Conversely, any such matrix is the adjacency matrix of a graph. We denote by $Z(G)$ the dimension of the kernel (that is, the subspace of eigenvectors with eigenvalue $0$) of the adjacency matrix of $G$.

**Induced subgraph**: If $V' \subset V$, the graph with vertex set $V'$ and edge set $E'$ those edges in 