Let \(G\) be a simple graph on a finite vertex set with \(n \ge 3\) vertices, and write \(E\) for its number of edges. If \(E + 6 \le 3n\) — equivalently \(E \le 3n - 6\) — then \(G\) has a vertex of degree at most \(5\); that is, the minimum degree of \(G\) satisfies \(\delta (G) \le 5\).

Let \(G\) be a simple graph on a finite vertex set \(V\) with \(n = \left\lvert V\right\rvert \) vertices, and let \(G^{c}\) denote its complement, the simple graph on \(V\) in which two distinct vertices are adjacent precisely when they are not adjacent in \(G\). Then the number of edges of \(G\) together with the number of edges of \(G^{c}\) equals the number of unordered pairs of vertices,

Let \(G\) be a simple graph on a finite vertex set \(V\) with \(n = \left\lvert V\right\rvert \ge 11\), write \(E(G)\) for its edge set, and let \(G^{c}\) be its complement (the simple graph on \(V\) in which two distinct vertices are adjacent exactly when they are not adjacent in \(G\)). Then \(G\) and \(G^{c}\) cannot both satisfy \(\left\lvert E(G)\right\rvert + 6 \le 3n\) and \(\left\lvert E(G^{c})\right\rvert + 6 \le 3n\); that is, at least one of the two graphs has more than \(3n - 6\) edges.

Let \(H\) be a subgraph of a finite simple graph \(G\), and let \(e\) and \(e'\) be edges of \(G\) that do not belong to \(H\), so both lie in \(E(G)\setminus E(H)\). Recall that two such edges are called equivalent when they are joined by a walk, internally disjoint from \(H\), whose first and last edges are the two given ones, and that the bridge of \(H\) containing an edge \(f\) is the subgraph of \(G\) induced by the equivalence class of \(f\). Write \(B\) for the bridge containing \(e\) and \(B'\) for the bridge containing \(e'\). If \(e\) and \(e'\) are not equivalent, then every vertex lying in both \(B\) and \(B'\) is a vertex of \(H\); that is, \(V(B)\cap V(B')\subseteq V(H)\).

Let \(G\) be a finite simple graph, let \(H\) be a subgraph of \(G\), and let \(e\) be an edge of \(G\) that does not belong to \(H\). Then the bridge of \(H\) in \(G\) containing \(e\) — the subgraph induced by the \(\sim \)-equivalence class of \(e\) — is connected: it has at least one vertex, and any two of its vertices are joined by a path within it.

Let \(G\) be a finite simple graph, let \(H\) be a subgraph of \(G\), and let \(e\) be an edge of \(G\) that does not belong to \(H\). Then any two vertices of the bridge of \(H\) in \(G\) containing \(e\) are joined by a path in \(G\) that is internally disjoint from \(H\).

Let \(C\) be a cycle in a finite simple graph \(G\), and let \(e\) be an edge of \(G\) that does not lie on \(C\); write \(B\) for the bridge of \(C\) in \(G\) that contains \(e\). Suppose \(v_1, v_2, v_3\) are three distinct vertices of attachment of \(B\), that is, three distinct vertices each lying both in \(B\) and on \(C\). Then there exists a vertex \(v_0\) of \(B\) that does not lie on \(C\), together with three paths \(P_1, P_2, P_3\) in \(G\) joining \(v_0\) to \(v_1\), \(v_2\), and \(v_3\) respectively, such that any two of these paths have only the vertex \(v_0\) in common.

Let \(G\) be a finite simple graph, let \(C\) be a cycle in \(G\), and let \(e\) and \(e'\) be edges of \(G\) that do not lie on \(C\); write \(B\) and \(B'\) for the bridges of \(C\) containing \(e\) and \(e'\) respectively. If \(B\) and \(B'\) overlap, then either they are skew, or their sets of vertices of attachment to \(C\) coincide and consist of exactly three vertices — that is, \(B\) and \(B'\) are equivalent \(3\)-bridges.

Let \(G\) be a finite connected simple graph that is not Hamiltonian, and let \(C\) be a longest cycle in \(G\) — a cycle whose length is at least that of every cycle of \(G\). Then there is an edge \(e \in E(G) \setminus E(C)\) such that the bridge of \(C\) containing \(e\) has a vertex that does not lie on \(C\).

Let \(G\) be a finite connected graph, and let \(C\) be a longest cycle of \(G\), with its vertices listed in cyclic order as \(v_0, v_1, v_2, \dots \) (so \(v_k\) is the vertex reached after \(k\) steps along \(C\), and \(v_{k+1}\) is its successor). Let \(e\) be an edge of \(G\) that does not lie on \(C\), and let \(B\) be the bridge of \(C\) that contains \(e\); suppose \(B\) has at least one vertex not lying on \(C\). If \(v_i\) and \(v_j\) are two distinct vertices of attachment of \(B\) to \(C\), then \(v_{i+1}\) and \(v_{j+1}\) are not adjacent in \(G\).

Let \(G\) be a finite simple graph on at least three vertices, and suppose \(G\) is connected. Write \(\alpha (G)\) for the independence number of \(G\) (the largest size of a set of pairwise nonadjacent vertices) and \(\kappa (G)\) for its vertex connectivity. If \(\alpha (G) \le \kappa (G)\), then \(G\) is Hamiltonian; that is, \(G\) has a cycle passing through every vertex exactly once.

Let \(G\) be a finite simple graph that is \(3\)-regular, so every vertex has exactly three neighbours, and suppose \(G\) admits a Hamiltonian cycle, a closed walk that visits every vertex exactly once. Then the line graph of \(G\) — whose vertices are the edges of \(G\), two being adjacent precisely when they share an endpoint — is \(3\)-colourable; equivalently, the edges of \(G\) can be properly coloured with three colours, a Tait colouring.