Results 1 to 7 of 7

Math Help - Graph theory

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    23

    Graph theory

    1.Is there a graph with degrees 1,2,2,2,3,3,4,4,4,5,5,7,7?
    2.Is there a bipatite graph with degrees 3,3,3,3,3,5,6,6,6,6,6,6?
    3.Is there a simple graph with degrees 1,1,4,4,4,6,6,7,8?

    Either give such a graph or prove that no such graph exists.


    (2)
    (i)For each of the graph in figure 10.5, label the vertices and edgrs and write down the adjacency matrix of the graph.
    (ii)Let G be any bipartite graph whose vertex set is partitioned into the subset{v1,v2,v3,...,vn}and{w1,w2,w3,...,wn}. What can you say about the adjacency matrix of G?


    /I try do it but I can't./
    Last edited by calfever; January 10th 2010 at 01:01 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2009
    Posts
    9
    Hello,

    1. This is how I would do the first one :
    What you have to do is to try to reduce degrees gradually until you get a sequence of degrees which obviously are the degrees of a graph, for example (0,0,0,0,0). So, what we're actually doing is deleting the last degree , and then we subtract 1 from as many members as was the last number of sequence (the one that you 'deleted'). Also, you keep the sequence sorted all the time, like in the beginning. In your example it will be:

    (1,2,2,2,3,3,4,4,4,5,5,7,7) ----> (1,2,2,2,2,3,3,3,3,4,4,6)
    (1,2,2,2,2,3,3,3,3,4,4,6) ----> (1,2,2,2,2,2,2,2,2,3,3)
    (1,2,2,2,2,2,2,2,2,3,3) ----> (1,1,1,2,2,2,2,2,2,2)
    (1,1,1,2,2,2,2,2,2,2) ---> (1,1,1,1,1,2,2,2,2)
    (1,1,1,1,1,2,2,2,2) ---> (1,1,1,1,1,1,1,2)
    (1,1,1,1,1,1,1,2) ---> (0,0,1,1,1,1,1)
    (0,0,1,1,1,1,1) ---> (0,0,0,1,1,1)
    (0,0,0,1,1,1) ---> (0,0,0,0,1)

    We got (0,0,0,0,1) which means that your sequence doesn't represent degrees of a graph. You can prove it in 2 ways: either showing that graph with 5 vertexes cannot have only one with degree 1, because every edge needs 2 vertex. Or you can just continue with this proces and show that in the next step you will get (-1,0,0,0), which is of course impossible, because vertex cannot have negative degree.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by calfever View Post
    1.Is there a graph with degrees 1,2,2,2,3,3,4,4,4,5,5,7,7?
    Heard of the most basic result of Graph Theory? The "handshake lemma"?

    \sum_{g\in G}\text{deg}(g)=2\left|E\right| where G=\left(V,E\right). If the graph above is G then \sum_{g\in G}\text{deg}(g)=35. See a problem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2009
    Posts
    9
    Quote Originally Posted by Drexel28 View Post
    Heard of the most basic result of Graph Theory? The "handshake lemma"?
    Yeah, it's definitely much better way to solve the problem! : ))
    However, in those examples where the sum is an even number, I think it's the best and quickest way to use the first method..
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    well, the first and third of the first assignment are pretty easy as the others stated...
    the second is just as easy, though the "first method" can't be applied here because the graph is bipartite which means some vertices CAN'T have edges to some other vertices. what you need to do is find a way such that the sum of the x-vertices' degrees equal to the y-vertices' degrees since each edge go from x to y and hence adds 1 to both. there's no way to do that with those degrees (the 5 screws it up), hence no, there is no such graph.

    2 (i) is easy, just label them and do an adjancy matrix...
    Adjacency matrix - Wikipedia, the free encyclopedia

    (ii) as i said before, the sum of the degrees of v1..vn equals the sum of the degrees of w1..wn.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2009
    Posts
    23
    for problems 1. 2. 3. I can do.


    (2)I can do an adjacency matrix but I suspect that method that do the adjacency of graphs(null graph,complete graph) same as the adjacency matrix of a bipartite graph?????

    I want example an adjacency matrix of a bipartite graph.

    thanks a lot.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    well, here's the adjacency matrix for 2(i)a):

    0 1 0 1 0 0 0 0 0
    1 0 1 0 1 0 0 0 0
    0 1 0 0 0 1 0 0 0
    1 0 0 0 2 0 1 0 0
    0 1 0 2 0 2 0 1 0
    0 0 1 0 2 0 0 0 1
    0 0 0 1 0 0 0 1 0
    0 0 0 0 1 0 1 0 1
    0 0 0 0 0 1 0 1 0

    i started from left to right, top to bottom.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 06:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM

Search Tags


/mathhelpforum @mathhelpforum