Results 1 to 6 of 6

Math Help - undirected graph questions

  1. #1
    Newbie
    Joined
    Feb 2013
    From
    texas
    Posts
    4

    undirected graph questions

    a. Let G be an undirected graph with n vertices. If G is isomorphic, to its own complement how many edges must G have? (Such a graph is called self-complementary.)



    b. Find an example of a self-complementary graph on four vertices and one on five vertices.


    c. If G is a self-complementary graph on n vertices, where n > 1, prove that n=4k or n=4k+1, for some k∈Z+ (I think this is k subset of Z+)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,708
    Thanks
    1638
    Awards
    1

    Re: undirected graph questions

    Quote Originally Posted by globalpro View Post
    a. Let G be an undirecthed graph with n vertices. If G is isomorphic, to its own complement how many edges must G have? (Such a graph is called self-complementary.)
    A complete graph of order n,~\mathcal{K}_n has \binom{n}{2}=\frac{n(n+1)}{2} edges.

    If \mathcal{G} has n vertices then \mathcal{G}\cup\overline{\mathcal{G}}=\mathcal{K}_  n.
    So how many edges does \mathcal{G} have?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2013
    From
    texas
    Posts
    4

    Re: undirected graph questions

    Thanks
    I really don't remember group theroy from 50 years ago. Some of the notations just don't make sense and I think that is the problem.

    So the answer to (b) for the 4 V would be a 10 edge solution and for the 5 V it would be 15 edges.

    And on (c) since I don't know what k or Z represent, best guess would be G has k subgraphs and Z represents all the possibles

    I told my grandson that when he asked for my help in the first place.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2013
    From
    texas
    Posts
    4

    Re: undirected graph questions

    Quote Originally Posted by Plato View Post
    A complete graph of order n,~\mathcal{K}_n has \binom{n}{2}=\frac{n(n+1)}{2} edges.

    If \mathcal{G} has n vertices then \mathcal{G}\cup\overline{\mathcal{G}}=\mathcal{K}_  n.
    So how many edges does \mathcal{G} have?
    How many kids have you helped flunk? Luckily I drew out the graphs and realized that the true answer is n(n-1)/2 for the number of edges on a undirected graph. Now do you have any suggestions on the C. portion of the question?

    c. If G is a self-complementary graph on n vertices, where n > 1, prove that n=4k or n=4k+1, for some k∈Z+ (I think this is k subset of Z+) Maybe you can mislead me enough that I can answer it for him.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: undirected graph questions

    Quote Originally Posted by globalpro View Post
    So the answer to (b) for the 4 V would be a 10 edge solution and for the 5 V it would be 15 edges.
    A self-complementary graph on 4 vertices has 3 edges, and the on on 5 vertices has 5 edges.

    Quote Originally Posted by globalpro View Post
    How many kids have you helped flunk? Luckily I drew out the graphs and realized that the true answer is n(n-1)/2 for the number of edges on a undirected graph.
    No need to be angry because of one typo that replaced a - with a +.

    Quote Originally Posted by globalpro View Post
    c. If G is a self-complementary graph on n vertices, where n > 1, prove that n=4k or n=4k+1, for some k∈Z+ (I think this is k subset of Z+) Maybe you can mislead me enough that I can answer it for him.
    Here k is the number of edges (this is not a part of the problem statement; it is a hint). Also, use (a generalization of) Euclid's lemma.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    643
    Thanks
    258

    Re: undirected graph questions

    If two graphs are isomorphic, they both have the same number of edges. As Plato points out, then the number of edges of a self-complmentary graph must be n(n-1)/4, where n is the number of vertices. (the complete graph on n vertices has n(n-1)/2 edges). So for part c, n(n-1)/4 must be an integer. Suppose n is of the form 4k+2 with k an integer, then n(n-1)/4=(4k+2)(4k+1)/4=(2k+1)(2k+1/2)=4k^2+3k+1/2. If this last expression were an integer, 1/2 would be an integer,
    tilt. Similarly, if n=4k+3. So the only possibilities left are n=4k or n=4k+1.

    If you know about congruence of integers, namely a is congruent to b mod m iff m divides a-b. It's much easier to compute mod 4.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 14th 2011, 11:31 PM
  2. question about graphs / undirected tree
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 13th 2011, 12:58 PM
  3. Help with graph questions please
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 11th 2010, 06:46 PM
  4. Cycles in an undirected graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2009, 12:30 AM
  5. More Graph Questions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 7th 2008, 03:39 PM

Search Tags


/mathhelpforum @mathhelpforum