0
$\begingroup$

i am inexperienced in the field of graph theory however i am attempting some questions that seem to be around my level however i cannot wrap my head around these questions despite having made several attempts at drawing graphs and wasting a lot of paper.

the main problem am having is that am trying to understand why a simply connected graph with 6 vertices (two of the vertices have a degree of 5) and 9 arcs cannot have any vertices of degree 1 and i have a feeling that the answer is obvious but like i said am pretty inexperienced in this area.

I am familiar with the theory that any simple graph has a total degree of twice the number of arcs and so in this case the total degree would be 18 but am not sure if that is of any help to my main problem

any help would be much appreciated

$\endgroup$
2
$\begingroup$

Start drawing the graph: make $6$ vertices, and draw in enough edges so that two of the vertices are of degree $5$. There’s only one way to do it. How many edges do you have at this point? Do you have any vertex of degree $1$?

$\endgroup$
  • $\begingroup$ i have a graph with 6 vertices and two of them have a degree of 5 but none of them have a degree of 1, if i added a vertex with a degree of one would the graph no longer be simply connected? $\endgroup$ – Zochonis Oct 30 '16 at 21:22
  • $\begingroup$ @A.Kennedy: If you add another vertex and give it degree $1$, you no longer have a graph with $6$ vertices and $9$ edges! $\endgroup$ – Brian M. Scott Oct 30 '16 at 21:23
  • $\begingroup$ oh am just not focusing tonight :/ thanks Brian! $\endgroup$ – Zochonis Oct 30 '16 at 21:26
  • $\begingroup$ @A.Kennedy: You’re welcome! (We’ve all had nights like that.) $\endgroup$ – Brian M. Scott Oct 30 '16 at 21:27

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.