Results 1 to 2 of 2

Math Help - Simple graph proof question

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    2

    Simple graph proof question

    Hi,

    I have an exercise about graphs which I cannot solve. Could you please help me?

    The exercise is as follows:

    A simple graph, also called a strict graph, is an unweighted, undirected graph containing no graph loops or multiple edges. A well-known theorem states that the sum of the degrees of the vertices of a simple graph equals twice the number of edges of the graph.

    Prove the following:

    There is no simple graph with 12 vertices and 28 edges so that

    (i) all vertices have degree 3 or 4
    (ii) all vertices have degree 3 or 6
    Thank you very much
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,901
    Thanks
    1756
    Awards
    1
    Notice that 2(28)=56.
    So (i) is impossible.

    For (ii) let s be the number of degree six vertices and t be the number of degree three.
    Then 6s+3t=56~\&~s+t=12.
    What is wrong with that?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: October 27th 2010, 08:30 PM
  2. Simple Proof Question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 23rd 2010, 11:23 PM
  3. Simple question on proof formalism
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: August 23rd 2010, 03:54 AM
  4. Very simple graph question
    Posted in the Geometry Forum
    Replies: 1
    Last Post: April 20th 2009, 11:17 AM
  5. Simple graph question (conflicting solution)
    Posted in the Geometry Forum
    Replies: 1
    Last Post: October 31st 2006, 11:46 PM

Search Tags


/mathhelpforum @mathhelpforum