Question

Does there exist a simple graph with 6 vertices of degree 1,2,2,4,5,5? if not, why? and if there is how do I draw it!?

Answer 1

omg graph theory is cool let me think

Answer 2

have you ever heard of the degree sequence algorithm

Answer 3

Write it in decreasing order

Answer 4

Should be no, since 2 of the vertices are connected to every other vertex. Why is this a contradiction?

Answer 5

(5,5,4,2,2,1) since 5 is the first number, the algorithm says to remove it and take 1 away from the 5 numbers after

Answer 6

yes you are correct bond

Answer 7

(4,3,1,1,0)

Answer 8

repeat the algorithm

Answer 9

rings a bell myin, go with that one for the proof, but it's good to understand why

Answer 10

4 is the first number now take 1 away from the four numbers after is and you get (2,0,0,-1) but you cant have a vertice with degree 1

Answer 11

so there is no simple graph with (5,5,4,2,2,1)

Answer 12

it is good to understand why, but I never knew why lol i don;t think

Answer 13

I just meant for this problem which has a simple contradiction, I don't think I could do it if it got any more complex.

Answer 14

Do you know if the algorithm always works? I don't remember.

Answer 15

as long as you dont have mixed graphs

Answer 16

Also, sorry fort butting in :-[

Answer 17

why? remember i like your number theory style so i think you are cool