Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: [Discrete Math] Pseudograph's

  1. Apr 16, 2006 #1
    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!
  2. jcsd
  3. Apr 16, 2006 #2
    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.
  4. Apr 16, 2006 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member


    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?


    I didn't see "the inverse of G is connected" stated in the definition of "the inverse of G". :tongue:
  5. Apr 16, 2006 #4
    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.
  6. Apr 16, 2006 #5
    "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).
  7. Apr 16, 2006 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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...
  8. Apr 16, 2006 #7
    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?
  9. Apr 16, 2006 #8
    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.
  10. Apr 16, 2006 #9


    User Avatar
    Science Advisor

    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?
  11. Apr 16, 2006 #10
    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).
  12. Apr 16, 2006 #11


    User Avatar
    Science Advisor

    The statement of Q1 is true if and only if the sum is even. See my post above.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook