# Graph theory basics: the size of a vertex set of a regular graph and a graph with $\Delta=4$.

Can someone tell me the answer to these?

1. Determine $|V|$ given that $G(V,E)$ is a regular graph with $E=12$.
2. If $G(V,E)$ be connected undirected graph what is largest value of $|V|$, if $|E|=19$ and $\deg(v)\ge 4$ for all $v\in V$.
-
We're here to help you come up with answers, not just give them to you. What progress have you made so far? –  Alexander Gruber Dec 29 '12 at 18:08
(-1) for "Can someone tell me the answer". –  TMM Dec 29 '12 at 18:21
(1) A $12$-cycle is a $2$-regular graph with $12$ edges and $12$ vertices. The union of two copies of $K_4$ is a $3$-regular graph with $12$ edges and $8$ vertices. Thus, $|V|$ cannot be uniquely determined from the given data. The best you can hope to do is limit the possibilities. Since $G$ is regular, there is a $d$ such that $\deg(v)=d$ for all $v\in V$. Then $$\sum_{v\in V}\deg(v)=d|V|\;.$$ By the handshaking formula we know that $$\sum_{v\in V}\deg(v)=2|E|=2\cdot 12=24\;.$$ So what are the possibilities for $|V|$?
(2) You know that $$38=2\cdot19=2|E|=\sum_{v\in V}\deg(v)\ge 4|V|\;.$$ This immediately gives you an upper bound on $V$, and you have to determine whether there is a connected graph with that number of vertices and $19$ edges.