Question

A certain connected graph has 68 vertices and 72 edges. Does it have a circuit?

Answer 1

Yes.

Explanation:

If a graph G doesn't have a circuit, we must have that

`|E(G)|=|V(G)|-1`

where
`|E(G)|` is the number of edges of the graph and
`|V(G)|` the number of vertices. However, in this case it holds that

`|E(G)|=72>68=|V(G)|.`