Let \(G\) be a general graph. The sum

of the degrees of all the vertices of \(G\) is an even number, and, consequently, the number of vertices of \(G\) with odd degree is even.

Two isomorphic general graphs have the same degree sequence, but two graphs with the same degree sequence need not be isomorphic.

Let \(G=(V, E)\) be a general graph. Then the vertex set \(V\) can be uniquely partitioned into nonempty parts \(V_1, V_2, \ldots , V_k\) so that the following conditions are satisfied: (1) The general subgraphs \(G_1=\left(V_1, E_1\right), G_2=\left(V_2, E_2\right), \ldots , G_k= \left(V_k, E_k\right)\) induced by \(V_1, V_2, \ldots , V_k\), respectively, are connected.
(2) For each \(i \neq j\) and each pair of vertices \(x\) in \(V_i\) and \(y\) in \(V_j\), there is no walk that joins \(x\) and \(y\).

Let \(G\) and \(G^{\prime }\) be two general graphs. Then the following are necessary conditions for \(G\) and \(G^{\prime }\) to be isomorphic: (1) If \(G\) is a graph, so is \(G^{\prime }\).
(2) If \(G\) is connected, so is \(G^{\prime }\). More generally, \(G\) and \(G^{\prime }\) have the same number of connected components.
(3) If \(G\) has a cycle of length equal to some integer \(k\), then so does \(G^{\prime }\).
(4) If \(G\) has an (induced) general subgraph that is a complete graph \(K_m\) of order \(m\), so does \(G^{\prime }\).

Let \(G = (V, E)\) be a general graph and assume that the degree of each vertex is even. Then each edge of \(G\) belongs to a closed trail and hence to a cycle.

Let \(G\) be a connected general gmph. Then \(G\) has a closed Eulerian trail if and only if the degree of each vertex is even.

Let \(G\) be a connected general graph. Then \(G\) has an open Eulerian trail if and only if there are exactly two vertices \(u\) and \(v\) of odd degree. Every open Eulerian trail in \(G\) joins \(u\) and \(v\).

Let \(G\) be a connected general graph and suppose that the number of vertices of \(G\) with odd degree is \(m {\gt} O\). Then the edges of \(G\) can be partitioned into \(m/2\) open trails. It is impossible to partition the edges of \(G\) into fewer than \(m/2\) open trails.

Let \(G\) be a connected general graph having \(K\) edges. Then there is a closed walk in \(G\) of length \(2K\) in which the number of times an edge is used equals twice its multiplicity.

A connected graph of order \(n \geq 3\) with a bridge does not have a Hamilton cycle.

Let \(G\) be a graph of order \(n \geq 3\) that satisfies the Ore property. Then \(G\) has a Hamilton cycle.

A graph of order \(n\), in which the sum of the degrees of each pair of nonadjacent vertices is at least \(n - 1\), has a Hamilton path.

A multigraph is bipartite if and only if each of its cycles has even length.

Let \(G\) be a bipartite graph with bipartition \(X, Y\). If \(|X| \neq |Y|\), then \(G\) does not have a Hamilton cycle. If \(|X|=|Y|\), then \(G\) does not have a Hamilton path that begins at a vertex in \(X\) and ends at a vertex in \(X\). If \(X\) and \(Y\) differ by at least 2 , then \(G\) does not have a Hamilton path. If \(|X|=|Y|+1\), then \(G\) does not have a Hamilton path that begins at \(X\) and ends at \(Y\), or vice versa.

A connected graph of order \(n\) has at least \(n - 1\) edges. Moreover, for each positive integer \(n\), there exist connected graphs with exactly \(n - 1\) edges. Removing any edge from a connected graph of order \(n\) with exactly \(n-1\) edges leaves a disconnected graph, and hence each edge is a bridge.

A connected graph of order \(n \geq 1\) is a tree if and only if it has exactly \(n - 1\) edges.

Let \(G\) be a connected graph and let \(\alpha = \{ x,y\} \) be an edge of \(G\). Then \(\alpha \) is a bridge if and only if there does not exist a cycle of \(G\) containing \(\alpha \).

Let \(G\) be a connected graph of order \(n\). Then \(G\) is a tree if and only if \(G\) does not have any cycles.

A graph \(G\) is a tree if and only if every pair of distinct vertices \(x\) and \(y\) is joined by a unique path. This path is necessarily a shortest path joining \(x\) and \(y\); that is, a path of length \(d(x, y)\).

Let \(G\) be a tree of order \(n \geq 2\). Then \(G\) has at least two pendent vertices.

Every connected graph has a spanning tree.

Let \(T\) be a spanning tree of a connected graph \(G\). Let \(\alpha = \{ a,b\} \) be an edge of \(G\) that is not an edge of \(T\). Then there is an edge \(\beta \) of \(T\) such that the graph \(T^{\prime }\) obtained from \(T\) by inserting \(\alpha \) and deleting \(\beta \) is also a spanning tree of \(G\).

Let \(T_1\) and \(T_2\) be spanning trees of a connected graph \(G\). Let \(\beta \) be an edge of \(T_1\). Then there is an edge \(\alpha \) of \(T_2\) such that the graph obtained from \(T_1\) by inserting \(\alpha \) and deleting \(\beta \) is a spanning tree of \(G\).

A neutral game is converted into a positive game if a new edge joining the distinguished vertices \(u\) and \(v\) is added to the multigraph of the game.

The game determined by a multigraph \(G = (V, E)\) with distinguished vertices \(u\) and \(v\) is a positive game if and only if there is a subset \(U\) containing \(u\) and \(v\) of the vertex set \(V\) such that the induced multisubgraph \(G_U\) has two spanning trees, \(T_1\) and \(T_2\), with no common edges.

Let \(G = (V, E)\) be a graph. Then \(G\) is connected if and only if the graph \(T = (U, F)\) constructed by carrying out the preceding algorithm is a spanning tree of \(G\).

Let \(G = (V, E)\) be a graph and let \(u\) be any vertex of \(G\). Then \(G\) is connected if and only if the graph \(T = (U, F)\) constructed by carrying out the BF-algorithm is a spanning tree of \(G\). If \(G\) is connected, then, for each vertex \(y\) of \(G\), the distance in \(G\) between \(u\) and \(y\) equals \(D(y)\); and this is the same as the distance between \(u\) and \(y\) in \(T\).

Let \(G = (V, E)\) be a graph and let \(u\) be any vertex of \(G\). Then \(G\) is connected if and only if the graph \(T = (U, F)\), constructed by carrying out the preceding DF-algorithm, is a spanning tree of \(G\).

Let \(G = (V, E)\) be a weighted graph and let \(u\) be any vertex of \(G\). Then \(G\) is connected if and only if the graph \(T = (U, F)\) obtained by carrying out the preceding algorithm is a spanning tree of \(G\). If G is connected, then for each vertex \(y\) of \(G\), the weighted distance between \(u\) and \(y\) equals \(D(y)\), and this is the same as thf weighted distance between \(u\) and \(y\) in the weighted tree \(T\).

Let \(G = (V, E)\) be a weighted connected graph with weight function \(c\). Then the preceding greedy algorithm constructs a minimum weight spanning tree \(T = (V, F)\) of \(G\).

Let \(G = (V, E)\) be a weighted graph with weight function \(c\). Then Prim’s algorithm constructs a minimum weight spanning tree \(T = (V, F)\) of \(G\).