I want to compute $|V|$ for a regular graph with 15 edges. According to this lemma:
$\sum_{v \in V} deg(v)=2|E|$
Whatever $|V|$ is, it should satisfy the above lemma. Based on that fact that in a regular graph, all vertices have the same degree, and that $|V|$ is an integer:
$\sum k = 2*15=30$
The only way for it to be correct is that $k=2,3,5$, which results in $|V|=6,10,15$. For example, if all vertices have a degree of $5$, then:
$\sum 5 = 30$
$5 |V| = 30$
So,
$|V|=\frac{30}{5}=6$
This was my solution, but I saw another solution which looks a little odd to me. It is based on the assumption that:
In a regular graph, $deg(v)=|V|-1$.
which I think is not true. But anyway, this solution uses the above assumption to obtain:
$\sum (|V|-1)=30 \Rightarrow |V| ( |V| -1) =30$
$|V|^2 – |V| =30$
$(|V|-6)\cdot(|V|+5)=0$
Then it accepts $|V|=6$, because, the number of vertices can't be a negative number.
Now my question is: is that assumption "in a regular graph, $deg(v)=|V|-1$" correct? Which answer is correct?
Best Answer
It's not true that in a regular graph, the degree is $|V| - 1$. The degree can be 1 (a bunch of isolated edges) or 2 (any cycle) etc. In a complete graph, the degree of each vertex is $|V| - 1$.
Your argument is correct, assuming you are dealing with connected simple graphs (no multiple edges.) If they need not be connected, you miss the case $k=1$ with 30 vertices.