# graph theory

• Dec 28th 2012, 10:24 PM
panelopy123
graph theory
1)determine |v|,given that G=(v,e) is regular graph with 12 edges?2)let G=(V,E) be a connected graph.What is the largest possible value of|V| if |E|=16 and deg(v)>=5 for all v belonging V?
• Dec 29th 2012, 07:21 AM
Plato
Re: graph theory
Quote:

Originally Posted by panelopy123
1)determine |v|,given that G=(v,e) is regular graph with 12 edges?2)let G=(V,E) be a connected graph.What is the largest possible value of|V| if |E|=16 and deg(v)>=5 for all v belonging V?

You failed to say if these questions are about simple graphs or not.

Lets assume they are. You should know that $\displaystyle \sum\limits_{v \in V} {\deg (v)} = 2\left| E \right|$.
Then what is a regular graph? If you know that the answer to the first is immediate.

The complete graph $\displaystyle \mathcal{K}_6$ has each vertex of degree five.
However, $\displaystyle |E|=15$ and $\displaystyle \ne16$. If these are not simple graphs then we can add an edge,
• Dec 29th 2012, 08:10 PM
panelopy123
Re: graph theory
its a simple graph.