Graph Theory

Two graphs are equal if and only if they have the same vertices and the same edges.

Two graphs are equal if and only if they have some vertices and the same edges.

If G is a graph with n vertices, then the degree of each vertex of G is an integer between 0 and n − 1.

The sum of all vertex degrees is twice the number of edges

In any graph there are an even number of vertices with odd degree.

In any graph there are an even number of edges with odd degree.

We say that G is k-regular to mean that every vertex has degree k.

Let G be a graph with δ(G) ≥ 2. Then G contains a cycle.

Let G be a graph with δ(G) ≥ 0. Then G contains a cycle.

Let G be a graph with N(G) ≥ 2. Then G contains a cycle.

Any graph with n vertices and at least n edges contains a cycle

Any graph with n vertices and at least n-1 edges contains a cycle

Any graph with n+1 vertices and at least n edges contains a cycle

A walk is closed if the first and last vertices of the walk are the same, that is, if you finish at the same vertex at which you started.

A walk is open if the first and last vertices of the walk are the same, that is, if you finish at the same vertex at which you started.

A walk is a path if and only if it has no repeated vertices

walk is a path if and only if it has repeated vertices

A closed walk is a cycle if and only if the only repeated vertex is the first and last vertex

A closed walk is a cycle if and only if there is a repeated vertex at the first and last vertex

Any tree on n ≥ 2 vertices has a leaf.

Any tree on n ≥ 0 vertices has a leaf.

Any connected graph contains a spanning tree

Any connected graph on n vertices with precisely n − 1 edges is a tree

Any connected graph on n vertices with precisely n edges is a tree

Any acyclic graph on n vertices with precisely n − 1 edges is a tree.

Any acyclic graph on n vertices with precisely n edges is a tree.