1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory Problem

  1. Nov 27, 2007 #1
    Hi! I was given the following task:

    1. The problem statement, all variables and given/known data

    (a) Exhibit three nonisomorphic, connected graphs with five vertices and four edges.
    (b) Argue that every connected graph with five vertices and four edges is isomomorphic to one of the three in part (a).

    3. The attempt at a solution
    It's not very difficult to draw the graphs:
    http://i83.photobucket.com/albums/j315/dobry_den/graphs.jpg [Broken]

    I'm not very sure about my argument:

    The sum of deg(v) has to be 8 (I have 4 edges, each is shared by two vertices). Moreover, there are 5 vertices, so the only combinations of degrees are: (1,1,1,1,4), (1,1,2,2,2) and (1,1,1,2,3).

    (i) There's no other way how to connect (1,1,1,1,4) vertices to yield a nonisomorphic graph with the (1,1,1,1,4) graph from point (a). This is quite clear.

    (ii) The same for a (1,1,2,2,2) graph.. This is a path and there's no other nonisomorphic connected graph that could be constructed from these vertices (eg. a graph consisting of a triangle and a path of length 1 has also vertices of degrees (1,1,2,2,2)..but it isn't connected).

    (iii) To ensure that a (1,1,1,2,3) graph is connected, the vertices with degrees 3 and 2 must share an edge (otherwise, there would be no path from the former to the latter.. since the rest of the vertices are of deg=1.. and that would yield a graph that's not connected).. thus all graphs with the degree set (1,1,1,2,3) are isomorphic with the one on the picture.

    Do you think this is sufficient? Thanks in advance
    Last edited by a moderator: May 3, 2017
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted