Results 1 to 3 of 3

Math Help - graph theory problem

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    26

    graph theory problem

    The friendship graph is defined as follows: the vertices are people,
    and we draw an edge between two people if they are friends. There are two kinds of people in the world: normal and strange. A normal person has an even number of friends, and a strange person has an odd number of friends.
    (a) Prove that there are at least two people in the world with the same number of friends.
    (b) Use the first theorem of graph theory to prove that there are an even
    number of strange people in the world.
    (c) If there are exactly two strange people in the world, prove that there is a path connecting them in the friendship graph.


    Alright so the first theorem of graph theory is that SUM(deg(v))=2|E| where v=# vertices in the graph and E=# of edges in the graph

    a) not too sure how to prove this....
    b) Would this be an appropriate proof:

    According to the first theorem of graph theory, the SUM(deg(v))=2|E|. Since the the people who are "strange" have an odd number of friends, that means the degree of those vertices are odd. Since adding an odd number of odd numbers together results in an odd number, and adding an even number of odd numbers together results in an even number. In order for the equation SUM(deg(v))=2|E| to hold, the SUM(deg(v)) must be divisible by two, and therefore the SUM(deg(v)) must be even. Therefore there must be an even number of "strange" people in the world.

    c) I don't know what to do for this part but I know I need to use this theorem:

    If Gi is a connected component of G then degGi(u)=degG(u) for any u in vi.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    Hi girlie,

    (a) depends on what kind of world you live in. If there's only one person in the world the statement is false. So let's suppose there are at least two (and finitely many) people in the world. That is, our graph has n>1 vertices. For every vertex v, there are n possible values of deg(v): namely 0,1,...,n-1. Assume, for contradiction, that no two vertices have the same degree. Then, since there are n vertices and n possibilities for a degree, we can number the vertices such that the first vertex has degree 0, the second vertex has degree 1, the third vertex has degree 2,..., the n-th vertex has degree n-1. But now we see there is no graph with these degrees of vertices: since the first vertex has degree 0, the n-th vertex can have degree at most n-2, a contradiction.

    (b) You have this correct. I wanted to add "Vertices of even degree don't play no role as to parity of SUM(deg(v))" but I guess it is too obvious.

    (c) Suppose there are exactly two vertices v_1, v_2 of odd degree in G and there's no path connecting them. Then the connected component G_1 of G containing the vertex v_1 doesn't contain v_2. So G_1 is a graph that contains exactly one vertex of odd degree (this is where we applied the theorem you mentioned). But this contradicts part (b).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    26
    thanks so much for the help!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 08:36 PM
  2. Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2009, 12:50 PM
  3. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 16th 2009, 09:33 AM
  4. A graph theory problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 15th 2009, 11:08 AM
  5. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 10:08 PM

Search Tags


/mathhelpforum @mathhelpforum