Data Structures and Notation

G=(V,E) is a graph, with V as its vertices (or nodes), and E as its edges (or links).

By convention, n = |V| and m = |E|. What's the largest m can be, assuming no edge appears more than once?

Often, we also have $m \ge n-1$ (connected, undirected graph).

For $u \in V$, we write $\mbox{\em Adj}[u]$ to be the set of vertices to which u is directly connected (i.e., $v \in \mbox{\em Adj}[u]$ if and only if $(u,v)\in E$ (adjacency list).

Note: Matrices also useful for representing edges: a_u,v = 1 if $(u,v)\in E$ and otherwise (adjacency matrix). If A is an adjacency matrix representing a graph G, which does A^T represent?