Suppose that it is given that the graph G has degree sequence 4,3,3,3,2,1, explain why this information is not sufficient to enable us to draw G

Question

javk · Answer

@Zarkon @Blonde_Gangsta @AngusV @SithsAndGiggles @FibonacciChick666 @rational @jtvatsim @UnkleRhaukus

fibonaccichick666 · Answer

hahahahahahahahahahahahahahahahahhahhahahahahaha oh goodness, I just finished this course

fibonaccichick666 · Answer

So quick answer is there is more than one graph with this degree sequence should this be graphical to begin with

fibonaccichick666 · Answer

|dw:1430266525771:dw|

fibonaccichick666 · Answer

well, you could do it another way

fibonaccichick666 · Answer

so we'd need to draw all possible combinations, we can't just make G

javk · Answer

ok, so is this answer correct:

There exist non-isomorphic graphs with the same degree sequence, so it is not possible to know what the graph looks like
e.g. in Graph A, the vertex with degree 1 is adjacent to a vertex with degree 3, whereas in Graph B, the vertex with degree 1 is next to a vertex with degree 4, therefore they are non-isomorphic

fibonaccichick666 · Answer

Yea, I like that.  I would say it is not possible to know exactly what it looks like though.

javk · Answer

well that's basically what we are showing, so this would be a prof by contradiction

fibonaccichick666 · Answer

yea, because you have more than one option.  The sequence is graphical as required, so since there is not just one graph with that sequence, we cannot know *exactly* what the graph looks like.  We can however list the possibilities of isomorphisms