Solving 5V 4E Graph Theory Problem

[dobry_den]

Hi! I was given the following task:

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

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

but i can't think of how i would argue... Do you have any idea? Thanks in advance!

 

[dobry_den]

Maybe I've come up with something.. 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?

 

[tacman]

Hi there! I can definitely help you with this problem. Graph theory can be a bit challenging, but once you understand the basics, it becomes much easier to solve problems like this one.

First, let's define what isomorphic means in terms of graphs. Two graphs are isomorphic if they have the same number of vertices and edges, and their structure is the same, meaning that the vertices are connected in the same way.

Now, for part (a), you have already successfully drawn three nonisomorphic, connected graphs with five vertices and four edges. This means that each graph has a unique structure, and you cannot rearrange the vertices or edges to make them look the same. This satisfies the first part of the task.

For part (b), we need to prove that every connected graph with five vertices and four edges is isomorphic to one of the three graphs you drew in part (a). To do this, we can use a technique called graph labeling. Essentially, we assign labels to the vertices and edges of a graph in a specific way, and if two graphs have the same labeling, then they are isomorphic.

In this case, we can label the vertices of each graph as A, B, C, D, and E. Then, for each graph, we can label the edges as follows:
- Graph 1: AB, AC, AD, BC
- Graph 2: AB, AC, AD, BD
- Graph 3: AB, AC, BC, CD

As you can see, each graph has a unique combination of edges, but they all have four edges and five vertices. This means that every connected graph with five vertices and four edges can be labeled in one of these three ways. Therefore, every connected graph with five vertices and four edges is isomorphic to one of the three graphs in part (a).

I hope this helps you understand how to approach and solve graph theory problems like this one. Keep practicing and you'll become a pro in no time!