need to do 2b and 3b. Here are the four distinct unlabelled graphs on five verti

Question

need to do 2b and 3b.

Here are the four distinct unlabelled graphs on five vertices and three edges: Each one represents an equivalence class of labelled graphs on five vertices and three edges. To verify that we have found all four unlabelled graphs: Determine the number of labelled graphs 011 live vertices and three edges. Use the Rule of Product, the Rule of Sum, or any other appropriate counting techniques to determine how many labelled graphs correspond to each of the four graphs above. (A good way to do this is to count the number of distinct ways you can assign labels to the vertices of the unlabelled graph.) Verily that the total number of labelled graphs you get is the same as the answer for part la. How many labelled graphs are there 011 live vertices and four edges? There are six different unlabelled graphs 011 five vertices and four edges. Draw each of these graphs, and then use the Rule of Sum, Rule of Product, or any other appropriate counting techniques to count the number of labelled graphs that correspond to it. Verify that the total number of labelled graphs you get is equal to the answer in part 2a. How many labelled graphs are there 011 live vertices and live edges? Find all the unlabelled graphs 011 five vertices with five edges. Count the number of labelled graphs that correspond to each one, and verify that the total number of labelled graphs you get is equal to the answer in part 3a.

Explanation / Answer

These include more sophisticated methods of counting sets. For example, the cardinalities of sequences of sets are often arranged into power series to form the generating functions, which can then be analyzed using techniques of analysis. (Since many counting procedures involve the binomial coefficients, it is not surprising to see the hypergeometric functions appear frequently in this regard.) In some cases the enumeration is asymptotic (for example the estimates for the number of partitions of an integer). In many cases the counting can be done in a purely synthetic manner using the "umbral calculus". Combinatorial arguments determining coefficients can be used to deduce identities among functions, particularly between infinite sums or products, such as some of the famous Ramanujan identities.

A non-enumerative branch of combinatorics is the study of designs, that is, sets and their subsets arranged into some particularly symmetric or asymmetric pattern. Perhaps most familiar are the Latin squares (arrangements of elements into a rectangular array with no repeats in any row or column). Also famous is the Fano plane (seven points falling into seven "lines", each with three points), which suggests the connection with finite geometries. (Suitably axiomatized, these tend to look like geometries over finite fields, although finite planes are much more flexible.) Matroids may be viewed as generalized geometries; they are included here as well. Of course graphs themselves are designs, although it is only the most regular graphs which are included in these discussions.

A graph is a set V of vertices and a set E of edges -- pairs of elements of V. This simple definition makes Graph Theory the appropriate language for discussing (binary) relations on sets, which is clearly a broad topic; a more detailed description is available on the index page for Graph Theory. Among the topics of interest are topological properties such as connectivity and planarity (can the graph be drawn in the plane?); counting problems (how many graphs of a certain type?); coloring problems (recognizing bipartite graphs, the Four-Color Theorem); paths, cycles, and distances in graphs (can one cross the K

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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