Which (if any) of the graphs below are the same? The graphs above are unlabeled.

Question

Which (if any) of the graphs below are the same? The graphs above are unlabeled. Usually we think of a graph as having a specific set of vertices. Which (if any) of the graphs below are the same? Actually, all the graphs we have seen above are just drawings of graphs. A graph is really an abstract mathematical object consisting of two sets V and E where E is a set of 2-element subsets of V. Are the graphs below the same or different? Graph 1: V = {a, b, c, d, e}, e = {{a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {d, e}}. Graph 2: V = {v_1, v_2, v_3, v_4, v_5}, E = {{v_1, v_3}, {v_1, v_5}, {v_2, v_4}, {v_2, v_5}, {v_3, v_5}, {v_4, v_5}}.

Explanation / Answer

1. The first figure has one vertex with degree 3 and the rest with degree 2. The second has degree of all vertices as 2. The third has two vertices with degree 3 and rest 2. The fourth has all vertices with degree 2. The fifth has a central vertex with degree 4.

So the second and fourth graphs are same.

2. In the first and second graphs, all edges have the same vertex pairs. The third has an edge bd which is not in the first two. The last one has different vertex labels but one to one correspondence with figure 2.

So the first, second and fourth graphs are same.

3. In Graph 1, a is paired with every other element. In Graph 2, v5 is mapped with all other elements. Both sets have same number of elements. The remaining two elements in Graph 1 are {b,c},{c,d} with no common elements. Similarly in Graph 2, the remaining elements are {v2,v4} and {v1,v3} which also do not have any common elements.

So the two graphs are same.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.