0
$\begingroup$

Let $G$ be a graph. Use the Handshake Theorem to prove that $\delta(G)\nu(G) \le 2\varepsilon(G) \le \Delta(G)\nu(G)$.

So the first step to solve this I know is that you need to know what everything stands for, like

  • $\delta(G)$= minimum degree
  • $\nu(G)$ number vertices,
  • $\varepsilon(G)$ number edges, and
  • $\Delta(G)$ = maximum degree $G$.

Then I know we use the formula $d(G) = 2\varepsilon (G)$. But this is where I get lost because I do not know how to apply the theorem. Any tips regarding how to solve this enigma would be kindly appreciated.

$\endgroup$
0
$\begingroup$

Handshake Theorem: $\sum_{v\in V(G)} d(v)=2\varepsilon(G)$.

Hence, $\delta(G)\nu(G)\leq\sum_{v\in V(G)} d(v)=2\varepsilon(G)\leq \Delta(G)\nu(G)$, where $V(G)$ is the vertex set of $G$.

$\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.