A certain graph has 19 vertices 16 edges and no circuits Is

A certain graph has 19 vertices, 16 edges, and no circuits. Is it connected?

Solution

No, it can\'t be. It has no non-trivial circuits, so if it were also connected, it would be a tree by definition. But we know that if a tree has n vertices, it must have n-1 edges. So if it were connected, it would have exactly 18 edges, which it doesn\'t.