1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.