CoCalc Public Files004 - Handouts / HW10 Solutions / hw10.sagews.htmlOpen with one click!
Authors: Mutiara Sondjaja, Drew Youngren
Views : 64
Compute Environment: Ubuntu 18.04 (Deprecated)
(File too big to render with math typesetting.)
Homework 10 Solutions

Homework 10 Solutions

AuthorDrew Youngren
Location004 - Handouts/HW10 Solutions/hw10.sagews
Original filehw10.sagews

Homework 10 Solutions

(1) How many edges does $K_n$, the complete graph on $n$ vertices, have?

Every size-2 subset of the vertices is an edge, so $K_n$ has $\begin{pmatrix} n \\ 2 \end{pmatrix}$ edges.

(2) How many graphs can be made on the set of vertices $\{1,2,3,\dots,n\}$?

$K_n$ has $\begin{pmatrix} n \\ 2 \end{pmatrix}$ edges, so any subset of them constitutes a unique graph. Thus, there are $2^{\begin{pmatrix} n \\ 2 \end{pmatrix}}$ grraphs.

(3) Let $\sim$ be the relation “is isomorphic to” on the set of all graphs with 4 vertices. Find a representative of each equivalence class. Hint: Organize them by number of edges.

(4) Exhibit two graphs that have the same number of vertices and edges but are not isomorphic.

Bonus: Exhibit two graphs with the same number of vertices and edges and the same number of vertices of a given degree, but are not isomorphic.

(5) Plot your answers here. See intro_to_graphs.sagews (start at line 49) for more examples, but the general format is:


Modify the example below to fit your needs.


(6–10) From Steinerman, do exercises §48.6,8,9,10,11 (p. 343).