A simple graph is a graph that does not have any loops or parallel edges. In a s

Question

A simple graph is a graph that does not have any loops or parallel edges. In a simple graph, an edge with endpoints v and w is denoted {v, w}. Draw all simple graphs with the four vertices {u, v, w, x} and two edges, one of which is {u, v}. Solution Each possible edge of a simple graph corresponds to a subset of two vertices. Given four vertices, there are ( ) = 6 such subsets in all: {u, v}, {u, w}, {u, x}, {u, w}, {v, x}, and {w, x}. Now one edge of the graph is specified to be {u, v}. so any of the remaining five from this list can be chosen to be the second edge. The possibilities are shown on the next page.

Explanation / Answer

The last figure which has two parallel edges is NOT a "simple graph" due to parallel edges because A simple graph, also called a strict graph, is an unweighted, undirected graph containing no graph loops or multiple edges As opposed to a multigraph, a simple graph is an undirected graph that has no loops and no more than one edge between any two different vertices. In a simple graph the edges of the graph form a set (rather than a multiset) and each edge is a distinct pair of vertices. In a simple graph with n vertices every vertex has a degree that is less than n (the converse, however, is not true — there exist non-simple graphs with n vertices in which every vertex has a degree smaller than n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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