0
$\begingroup$

I have graph built just like in the image: the red dots are the edges and the black lines are the arcs that connect them.

The only difference from the picture is that in my graph the arcs are double(two for each line in the picture). My question is: whats the the formula that gives me the exact number of arcs from my graph if I know the number of the base dots and the height dots?

I thought it would be arcs=total_dots_number*16-{[(2*base_dots)+(2*height_dots)-4)]*6+4*10} but it is apparently wrong.

graph

$\endgroup$
0
$\begingroup$

Recall that the handshaking lemma states that $\sum_{v\in V}deg(v)=2e$, where $e$ is the number of edges (arcs), $V$ is the set of vertices (dots), and $deg(v)$ is the number of edges incident with vertex $v$.

Suppose you have $m$ vertices in each column and $n$ vertices in each row. The degree of each of the four corner vertices is $6$. The degree of a non-corner vertex along the side is $10$. There are $2(n-2)+2(m-2)$ of these. Finally, the degree of an internal vertex is $16$. There are $(n-2)(m-2)$ of these. Hence, the total number of edges is $$\frac{4(6)+10(2(n-2)+2(m-2))+16(n-2)(m-2)}{2},$$ which I'll leave for you to simplify.

$\endgroup$
  • $\begingroup$ That's it! Can you explain me why there is a /2 in the formula? $\endgroup$ – W4lker Dec 8 '13 at 15:45
  • $\begingroup$ It's the $2$ from the handshaking lemma moved to the left hand side. $\endgroup$ – Casteels Dec 8 '13 at 16:34

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.