Question

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

Answer 1

Answer:

Yes.

Step-by-step 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)|.$