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:

Graph([list_of_vertices,list_of_edges])

Modify the example below to fit your needs.

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