Results 1 to 3 of 3

Math Help - 2 math questions about graph.

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    7

    2 math questions about graph.

    1. If G is a simple graph with 18 edges and its complement G also has 18 edges, how many vertices does G have?

    2. Fix a constant integer k 3. Suppose that a connected planar simple graph with e edges and v vertices contains no simple circuits of length k or less.
    Show that
    e ≤ [(k+1)/(k-1)](v 2) if v ≥ ⌈ (k+3)/2.




    I have weak basis on graph.. sigh.. thanks much
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: 2 math questions about graph.

    1. Note that if you take edges from G and its complement, you'll get a complete graph.

    2. This seems to be a generalization of the problem considered in this thread (where k = 3).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: 2 math questions about graph.

    Quote Originally Posted by kakatomy View Post
    1. If G is a simple graph with 18 edges and its complement G also has 18 edges, how many vertices does G have?

    If G has n vertices and so does its complement, \overline{G}.

    We know that G\cup\overline{G}=K_n.

    Thus \binom{n}{2}=36. Solve for n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with graph questions please
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 11th 2010, 06:46 PM
  2. discrete math: graph theory
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 27th 2009, 05:02 AM
  3. Replies: 5
    Last Post: January 4th 2009, 05:37 PM
  4. More Graph Questions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 7th 2008, 03:39 PM
  5. Math prob transformation of graph
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: March 9th 2007, 12:24 PM

Search Tags


/mathhelpforum @mathhelpforum