Graph Theory Problem: Nonisomorphic Connected Graphs with 5 Vertices and 4 Edges

[dobry_den]

Hi! I was given the following task:

Homework Statement

(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).

The Attempt at a Solution

It's not very difficult to draw the graphs:
http://i83.photobucket.com/albums/j315/dobry_den/graphs.jpg

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

 

[mighty2000]

!



Thank you for your question and for providing your thoughts and solutions so far. I would like to offer some insights and clarifications on your argument and also provide some additional information to support your solutions.

Firstly, your graphs in part (a) are correct and are the only non-isomorphic connected graphs with five vertices and four edges. This can be verified by using the isomorphism test, which checks for the preservation of adjacency, degree sequence, and path length in two graphs.

Secondly, your argument for part (b) is partially correct. You are correct in saying that the sum of degrees of the vertices in a connected graph with five vertices and four edges must be 8. However, there are actually four possible combinations of degrees: (1,1,1,1,4), (1,1,2,2,2), (1,1,1,2,3), and (1,2,2,2,1). The last combination is not possible in a connected graph, as it would result in two isolated vertices.

You are also correct in saying that there is no other way to connect the vertices in the (1,1,1,1,4) graph to yield a non-isomorphic graph. This is because this graph is a complete graph, meaning that every vertex is connected to every other vertex. In other words, there is only one way to draw this graph.

For the (1,1,2,2,2) graph, you are correct in saying that there is no other non-isomorphic connected graph that could be constructed from these vertices. This is because this graph is a cycle, meaning that each vertex is connected to exactly two other vertices, forming a loop. Again, there is only one way to draw this graph.

For the (1,1,1,2,3) graph, your argument is not entirely correct. While it is true that the vertices with degrees 3 and 2 must share an edge to ensure connectivity, there are actually two ways to draw this graph. One way is the graph shown in your solution, where the vertices with degrees 3 and 2 are connected by an edge. The other way is to have the vertices with degrees 2 and 3 connected by an edge, and the remaining vertices connected in a path. Both of these graphs are non-isomorphic, as they have different adjacency and path length structures.

In conclusion,