Math Problems Vault

Problem 2.3.1

Roughly speaking, graphs are isomorphic if they are the same (although their drawings in the plane may differ). Formally, graphs $G_{1}$ and $G_{2}$ are called isomorphic if there exists a one-to-one mapping $f: V(G_{1}) \to V(G_{2})$ satisfying the condition: vertices $A, B \in V(G_{1})$ are joined by an edge if and only if the vertices $f(A), f(B) \in V(G_{2})$ are joined by an edge.

Which of the graphs in Fig. 3 are isomorphic?

Fig. 3. Which of the graphs in the figure are isomorphic?

?

Problem 2.3.2

For arbitrary $k,l,m,n \in \mathbb {N}$ , find the number of

?

(1)

cliques of size $k$ in the graph $K_{n}$ ,

(2)

cliques of size $k$ in the graph $K_{m,n}$ ,

(3)

independent sets of size $k$ in the graph $K_{n}$ ,

(4)

independent sets of size $k$ in the graph $K_{m,n}$ ,

(5)

subgraphs of $K_{n}$ isomorphic to $K_{k,l}$ ,

(6)

subgraphs of $K_{m,n}$ isomorphic to $K_{k,l}$ .

Be careful: these problems are simple, but almost all of them require a case analysis.

Problem 2.3.3

(1)(2)(3)

List all pairwise non-isomorphic

?

(1)

graphs with four vertices,

(2)

connected graphs with five vertices and five edges,

(3)

disconnected graphs with five vertices.

Problem 2.3.4

How many pairwise non-isomorphic graphs with 8 vertices and 25 edges are there?

?

Problem 2.3.5

The number of isomorphism classes of trees with $n$ vertices (i.e., the number of distinct trees with $n$ unlabeled vertices) is less than $4^{n}$ .

?