Adjacency Matrix: For a graph $G = (V,E)$ with $n = |V|$ vertices, the adjacency matrix $A$ is an $n \times n$ matrix where: $A[i,j] = \begin{cases} 1 & \text{if } \{v_i, v_j\} \in E \\ 0 & \text{otherwise} \end{cases}$

For undirected graphs, $A$ is symmetric. For directed graphs, $A[i,j] = 1$ if there's an edge from $v_i$ to $v_j$.

Adjacency List: Store for each vertex a list of its neighbors. Space-efficient for sparse graphs.

Incidence Matrix: $n \times m$ matrix ($m = |E|$) where entry $(i,j)$ indicates whether vertex $i$ is incident to edge $j$.

Graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic, written $G_1 \cong G_2$, if there exists a bijection $f: V_1 \to V_2$ such that $\{u,v\} \in E_1$ if and only if $\{f(u), f(v)\} \in E_2$.

Isomorphic graphs have the same structure under relabeling. Determining whether two graphs are isomorphic is a famous problem: not known to be in P, but not proven NP-complete.

A subgraph of $G = (V,E)$ is a graph $H = (V', E')$ where $V' \subseteq V$ and $E' \subseteq E$.

An induced subgraph $G[V']$ includes all edges from $E$ with both endpoints in $V'$.

A spanning subgraph has $V' = V$.

A graph $H$ is a minor of $G$ if $H$ can be obtained from $G$ by deleting edges, deleting vertices, and contracting edges. Planar graphs are characterized by forbidden minors $K_5$ and $K_{3,3}$.

Chromatic number $\chi(G)$: Minimum number of colors needed to color vertices so adjacent vertices have different colors.

Clique number $\omega(G)$: Size of the largest complete subgraph.

Independence number $\alpha(G)$: Size of the largest independent set (no two vertices adjacent).

Edge connectivity $\kappa'(G)$: Minimum number of edges whose removal disconnects the graph.

Vertex connectivity $\kappa(G)$: Minimum number of vertices whose removal disconnects the graph.

Relationships: $\chi(G) \geq \omega(G)$ and $\chi(G) \cdot \alpha(G) \geq |V|$.