A graph is a set of vertices \(V\), a set of edges E which are subset of pairs from V.
undirected so each edge is a set
The degree of a vertex is the number of edges connections to it.
The order of a graph is the number of vertices, \(|V|\).
The size of a graph is the number of edges, \(|E|\).
We can take a subset of vertices, and all edges which only depend on these vertices. This is an induced subgraph.
A loop is an edge where both the vertices are the same.
If there are two edges with the same pair of indices, there are multiple edges.
No loops or multiple edges.
An edge-weighted graphs has weights for each edge.
A vertex-weighted graph has weights for each vertex.
We can represent a finite graph as a square matrix. \(m_{ij}\) is the number of edges connecting vertex \(i\) to vertex \(j\).
An incidence matrix has \(m_{ij}\) representing the number of connections from vertex \(i\) to edge \(j\).
A degree matrix is a diagonal matrix. Each diagonal contains the degree of the a vertex.
The Laplacian matrix \(L\) is formed using the degree matrix \(D\) and the adjacency matrix \(A\). \(L=D-A\).