Can a Pseudograph's Degree Sequence Form an Even Sum?

[Servo888]

Question 1
--------------------------------------------------
"Prove that if (d_1, d_2, ... d_n) is a sequence of natural numbers whos sum is even (n>=1) then there is a pseudograph with n vertcies such that vertex i has degree d_i for all i=1,2,...n"

So we have a sequence of natural numbers... Something like this; we have a sequence... 1+2+3+4+5+6+7...+d_n, and their sum is even. So if we have d_n verticies, and are on the vertex i=n, then vertex i has degree d_i, which is d_n. And that's true for any i.

But I'm not sure if that's just restating the question...

Question 2
--------------------------------------------------
Show that if graph G is not connected, then its complement is connected.

"In graph theory the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to find the complement of a graph, you fill in all the missing edges, and remove all the edges that were already there. It is not the set complement of the graph; only the edges are complemented."

How do I show this? I mean BY definition of completment, we see that the complement has to be connected, it's the inverse of G!

 

[Servo888]

Question 1:
WTF! This CANNOT be true... Say you have {1,2,3,4,5,6,7} (sum = 28), vertex i = 7, so d_7 should have a degree of 7, but that's impossible, the largest degree possible is 6.

 

[Hurkyl]

Q1:

There's no reason the (d_1, ..., d_n) need to be consecutive, distinct, or even in sorted order -- that's just one possibility.


Anyways, what makes a pseudograph different than a graph?



Q2:

I didn't see "the inverse of G is connected" stated in the definition of "the inverse of G".

 

[Servo888]

Q1:

There's no reason the (d_1, ..., d_n) need to be consecutive, distinct, or even in sorted order -- that's just one possibility.


Anyways, what makes a pseudograph different than a graph?


Q2:

I didn't see "the inverse of G is connected" stated in the definition of "the inverse of G".

Q1:
No clue... My book uses pseudograph, and my teacher calls them just graphs.

Q2: Well it's saying that if you have an edge connected by two vertices, then then complement would be two verticies with no edges.
So when we are told that G is not connected, then the inverse has to be connected.

 

[Servo888]

"A pseudograph is a graph that allows both parallel edges and loops."

Oh if you can have loops then yes you can have d_n (even more) degrees... Then the sum doesn't matter (at least I don't see it mattering).

 

[Hurkyl]

Oh if you can have loops then yes you can have d_n (even more) degrees... Then the sum doesn't matter (at least I don't see it mattering).

Okay, then look for a counterexample. The simplest possibility would be the graph with one vertex of degree 1.

(i.e. n = 1, and d_1 = 1)

P.S. don't forget that a loop is incident twice with its vertex, so a vertex with a loop and no other edges has degree 2.

No clue... My book uses pseudograph, and my teacher calls them just graphs.

Different fields of study might use different kinds of graphs -- for example, in one of my big interests (category theory), a "directed multigraph with loops" (i.e. a pseudograph with directed edges) is very important, and all of the category theory literature simply calls such things "graphs", because it would be to cumbersome to do anything else.

Q2: Well it's saying that if you have an edge connected by two vertices, then then complement would be two verticies with no edges.
So when we are told that G is not connected, then the inverse has to be connected.

Then prove it! You might want to review the definition of connected, though...

 

[Servo888]

Okay, then look for a counterexample. The simplest possibility would be the graph with one vertex of degree 1.

(i.e. n = 1, and d_1 = 1)

P.S. don't forget that a loop is incident twice with its vertex, so a vertex with a loop and no other edges has degree 2.



Different fields of study might use different kinds of graphs -- for example, in one of my big interests (category theory), a "directed multigraph with loops" (i.e. a pseudograph with directed edges) is very important, and all of the category theory literature simply calls such things "graphs", because it would be to cumbersome to do anything else.




Then prove it! You might want to review the definition of connected, though...

Q1: So with the counter example of just 1 vertex, it does not have 1 edge. The only possibility is a loop, but that would be 2 degrees. Is this what we're looking for, for the counter example?

 

[Servo888]

Edit, no, because we need the sum to be even.
But either way I see the light now, I think I can concat up something up.

 

[0rthodontist]

One easy way to think about Q1 is in terms of letting all edges that exit from nodes go into a central fictitious "hub," then removing the hub and connecting up the edges that are then loose.

For Q2, if the graph is not connected, then you know that its vertices can be partitioned (with more than one partition) so that for a given partition P, no vertex in P connects to any vertex in the nonempty set V - P. So in the graph's complement, what can be said about which vertices the vertices in P must connect to?

 

[Servo888]

I'm stuck on Q1... I mean I see it as being false, is this the right assumtion? Because the sum doesn't matter, since you can have parallel edges, you can always have d_i degrees (it's always true).

 

[0rthodontist]

The statement of Q1 is true if and only if the sum is even. See my post above.