Does there exist a graph with order 10 and size 9 but not a tree?

497 Views Asked by At

I am in graph theory and I have tried multiple ways to tackle this. I can't seem to find a connected graph G that fits order 10 (10 vertices) and size 9 (9 edges) and is not a tree. Is the graph disconnected? Any help would be great! Thank you.

1

There are 1 best solutions below

0
On

A graph with a cycle which has $n$ vertices also has $n$ edges in that cycle. Adding an edge can at most add one vertex, and you have $9-n$ edges and $10-n$ vertices, hence the graph will be disconnected.