Can a graph with 3 vertices have a ratio greater than 1 of edges to vertices

Question

A graph with three vertices has a beta index no greater than 1. A beta index of a graph is the ratio of number of edges to the number of vertices.

The answer key says true but I think it's false. If loops are allowed and vertex $A$ connects to vertex $A$ then there could be 6 edges in a graph and 3 vertices and clearly $\frac{6}{3} = 2 > 1$ Did the answer key assume that loops aren't allowed or am I missing something?

Latter on the textbook explains beta indexes are used by geographers to measure the connectedness between places, so maybe in that context it wouldn't make sense to have a place connected to itself.

Answer 1

The Beta index of a simple graph, meaning it has no loops or multiple edges between vertices, has a value no greater than $1$. It equals $1$ for a simple connected graph with $1$ cycle.

So, as to the answer to your question, yes, the answer key assumed that the graph is simple.

Answer 2

If the graph has no loops, then this would work (otherwise, as you said, you can have as many loops as you want.):

Use the fact that for a simple graph $G$ , we have $\Sigma Deg(G)=2|E(G)|$ .

Then you want to maximize the expression: $\frac {E(G)}{V(G)}$ .

Use above equation, together with the fact that $V(G)=3$ , and sub-in in the numerator, to get:

$\frac {\Sigma Deg(G)} {2 (3)}$= $\frac {\Sigma Deg(G)}{6}$. (##)

Now, a maximal connected graph without loops is a tree -- by definition a tree is minimally-connected, and maximally -acyclic-- so that a tree on $3$ edges maximizes the number of edges in the graph, giving you a bound. In a graph on 3 edges, each vertex has degree 2, so that $\Sigma Deg(G)=2+2+2=6$. Subbing-in in (##) above, you get:

$\frac {E(G)}{V(G)}\leq \frac {6}{6}=1 $, which gives you the bound of $1$ under the assumption that there are no loops.