Let \(G\) be a simple graph on a finite vertex set \(V\) and \(H\) a simple graph on a vertex set \(W\). Then \(G\) and \(H\) are isomorphic if and only if there is a bijection \(\theta \colon V \to W\) such that for all vertices \(u, v \in V\), the pair \(u, v\) is adjacent in \(G\) if and only if \(\theta (u), \theta (v)\) is adjacent in \(H\).

Let \(G\) be a simple graph on a finite vertex set \(V\) with \(n = \left\lvert V\right\rvert \) vertices. Then \(G\) has exactly \(\binom {n}{2}\) edges if and only if \(G\) is the complete graph on \(V\), that is, every pair of distinct vertices is adjacent.

For natural numbers \(m\) and \(n\), let \(K_{m,n}\) be the complete bipartite graph whose two parts have \(m\) and \(n\) vertices, with an edge joining every vertex of the first part to every vertex of the second and no edges within either part. Then \(K_{m,n}\) has exactly \(mn\) edges.

Let \(G\) be a simple graph on a finite vertex set \(V\) that is bipartite, i.e. admits a proper \(2\)-colouring. Then the number of edges of \(G\) satisfies

For every \(k \in \mathbb {N}\), the \(k\)-cube — the graph whose vertices are the length-\(k\) binary strings, two strings being joined by an edge precisely when they differ in exactly one coordinate — has exactly \(k \cdot 2^{k-1}\) edges.

For every \(k \in \mathbb {N}\), the \(k\)-cube \(Q_k\) — the graph whose vertices are the length-\(k\) strings of bits, two strings being adjacent precisely when they differ in exactly one coordinate — admits a proper colouring with two colours; that is, \(Q_k\) is bipartite.

Let \(G\) be a self-complementary simple graph on a finite vertex set \(V\); that is, \(G\) is isomorphic to its complement \(\overline{G}\). Then the number of vertices \(\left\lvert V\right\rvert \) satisfies \(\left\lvert V\right\rvert \equiv 0 \pmod4\) or \(\left\lvert V\right\rvert \equiv 1 \pmod4\).

Let \(V\) be a vertex set and let \(K_V\) denote the complete graph on \(V\), in which every pair of distinct vertices is adjacent. For any subset \(s \subseteq V\), the subgraph of \(K_V\) induced on \(s\) is again a complete graph, namely the complete graph \(K_s\) on the vertex set \(s\): any two distinct vertices of \(s\) are adjacent in the induced subgraph precisely because they are adjacent in \(K_V\).

Let \(G\) and \(H\) be simple graphs on a common finite vertex set, and suppose \(H\) is a subgraph of \(G\) (every edge of \(H\) is an edge of \(G\)). If \(G\) admits a proper vertex colouring with two colours, then so does \(H\).

Let \(G\) be a simple graph on a finite vertex set \(V\) that is \(2\)-colourable, meaning it admits a proper colouring with two colours. Then for every subset \(s \subseteq V\), the induced subgraph \(G[s]\) is again \(2\)-colourable.

Let \(G\) be a simple graph on a finite vertex set, and suppose \(G\) is bipartite, meaning its vertices can be properly colored with two colors so that adjacent vertices receive different colors. Let \(H\) be any subgraph of \(G\) — a simple graph on the same vertex set every edge of which is also an edge of \(G\) — and let \(s\) be any set of vertices. Then the subgraph of \(H\) induced on \(s\), obtained by keeping only the vertices in \(s\) together with those edges of \(H\) joining two vertices of \(s\), is again bipartite.

Let \(G\) be a simple graph on a finite vertex set \(V\), and for each vertex \(v\) write \(d(v)\) for its degree, the number of vertices adjacent to \(v\). Then

where \(\left\lvert E(G)\right\rvert \) is the number of edges of \(G\).

In a finite simple graph \(G\), the number of vertices whose degree is odd is even.

Let \(G\) be a simple graph on a finite, nonempty vertex set \(V\), and write \(n = |V|\) for the number of vertices and \(m\) for the number of edges. Let \(\delta (G)\) and \(\Delta (G)\) denote the minimum and maximum degree of \(G\), respectively. Then

Let \(G\) be a finite simple graph, and let \(k \ge 1\) be a positive integer such that every vertex of \(G\) has degree exactly \(k\). Suppose that \(G\) is bipartite with parts \(s\) and \(t\); that is, \(s\) and \(t\) are disjoint sets of vertices whose union contains every vertex, and every edge of \(G\) joins a vertex of \(s\) to a vertex of \(t\). Then the two parts have the same size, \(\left\lvert s\right\rvert = \left\lvert t\right\rvert \).

Let \(G\) be a finite simple graph with vertex set \(V\). Then \(G\) has a spanning subgraph \(H\) that is bipartite (that is, \(2\)-colourable) and in which every vertex keeps at least half of its original degree: writing \(d_G(v)\) for the degree of \(v\) in \(G\) and \(d_H(v)\) for the number of neighbours of \(v\) in \(H\), one has \(d_G(v) \le 2\, d_H(v)\) for every \(v \in V\).

Let \(G\) be a finite simple graph, and let \(L(G)\) denote its line graph, whose vertices are the edges of \(G\), with two such vertices adjacent precisely when the corresponding edges of \(G\) share a common endpoint. Then the number of edges of \(L(G)\) equals

where the sum runs over all vertices \(v\) of \(G\) and \(\deg _G(v)\) is the degree of \(v\).

Let \(G\) be a finite simple graph with minimum degree \(\delta (G)\), and let \(k\) be a natural number with \(k \le \delta (G)\). Then \(G\) contains a path of length exactly \(k\); that is, there exist vertices \(u\) and \(v\) and a path from \(u\) to \(v\) in \(G\) traversing exactly \(k\) edges.

Let \(G\) be a simple graph on a finite, nonempty vertex set \(V\). Then \(G\) is connected if and only if, for every set \(S \subseteq V\) such that both \(S\) and its complement \(V \setminus S\) are nonempty, there exist vertices \(u \in S\) and \(v \in V \setminus S\) that are adjacent in \(G\).

Let \(G\) be a finite simple graph on a vertex set of size \(n\), and write \(\left\lvert E(G)\right\rvert \) for its number of edges. If

then \(G\) is connected.

Let \(G\) be a simple graph on a finite, nonempty vertex set. If \(G\) is not connected, then its complement \(G^{c}\) — the simple graph on the same vertices in which two distinct vertices are adjacent precisely when they are non-adjacent in \(G\) — is connected.

Let \(H\) and \(K\) be two simple graphs on a common finite vertex set \(V\), and suppose \(H \le K\), meaning that every edge of \(H\) is also an edge of \(K\). Then \(K\) has no more connected components than \(H\); that is, the number of connected components of \(K\) is at most the number of connected components of \(H\).

Let \(G\) be a finite simple graph and let \(e\) be an edge of \(G\). Writing \(c(H)\) for the number of connected components of a graph \(H\), and \(G - e\) for the graph obtained from \(G\) by removing the edge \(e\) (keeping all vertices), one has

That is, deleting a single edge either leaves the number of connected components unchanged or increases it by exactly one.

Let \(G\) be a simple graph on a finite vertex set, and let \(G^{\mathrm{c}}\) denote its complement, the graph on the same vertices in which two distinct vertices are adjacent exactly when they are non-adjacent in \(G\). If the diameter of \(G\) is greater than \(3\), then the diameter of \(G^{\mathrm{c}}\) is less than \(3\).

Let \(G\) be a finite simple graph that is connected but not complete. Then there exist vertices \(u\), \(v\), \(w\) of \(G\) such that \(u\) is adjacent to \(v\) and \(v\) is adjacent to \(w\), yet \(u\) is not adjacent to \(w\).

Let \(G\) be a finite simple graph. Then \(G\) admits a proper vertex \(2\)-colouring — equivalently, its vertices can be partitioned into two independent sets — if and only if every cycle in \(G\) has even length.

Let \(G\) be a finite simple graph, and let \(c\) be a closed trail in \(G\) based at a vertex \(u\) — that is, a walk from \(u\) to \(u\) that traverses no edge more than once — of positive length. Then every edge \(e\) appearing in \(c\) lies on a cycle of \(G\): there is a vertex \(v\) and a cycle based at \(v\) whose edge set contains \(e\).

Let \(G\) be a finite simple graph whose minimum degree is at least \(2\), meaning every vertex has at least two neighbours. Then \(G\) contains a cycle: there is a vertex \(v\) and a closed walk from \(v\) to itself that is a cycle.

Let \(G\) be a finite simple graph whose minimum degree \(\delta (G)\) is at least \(2\). Then \(G\) contains a cycle of length at least \(\delta (G) + 1\).

Let \(G\) be a finite simple graph that is \(k\)-regular, meaning every vertex has exactly \(k\) neighbors, and suppose \(G\) has girth \(4\), that is, the length of its shortest cycle is \(4\). Then \(G\) has at least \(2k\) vertices.

Let \(G\) be a finite simple graph that is \(k\)-regular, meaning every vertex has exactly \(k\) neighbours, and suppose \(G\) has girth \(5\), so that its shortest cycle has length exactly \(5\). Then \(G\) has at least \(k^2 + 1\) vertices.

Let \(G\) be a finite simple graph on a nonempty vertex set \(V\), and write \(n\) for the number of vertices and \(m\) for the number of edges of \(G\). If \(n \le m\), then \(G\) contains a cycle: there exist a vertex \(v\) and a closed walk from \(v\) to \(v\) that is a cycle.