1

$A: m=5, 6$

$B: n=n_1 + n_2, m=n_1 n_2; n_1, n_2 >0$

$C: n=m$

$D: \forall v \in V(G), (n-1)-deg_v = 3$, which means $m=n(n-4)/2$.

Now consider every intersection.

$A \cap B$: $m=5=15; m=6 = 16 = 2*3$. Therefore $A \cap B= \{ K_{1,5}, K_{2,3}, K_{1,6} \}$.

$A \cap C: n=m=5,6$, therefore $A \cap C = \{ C_5, C_6 \}$.

$A \cap D:$ $n(n-4)=10,12 \implies n=m=6$. Therefore $A \cap C = \{ C_6 \}$.

$B \cap C$: $n_1 + n_2 = n_1 n_2 \implies n_1/(n_1-1)=n_2 \implies n_1 = n_2=2$. Therefore $B \cap C = \{ K_{2,2} \}$.

$B \cap D$: $2 n_1 n_2 = (n_1 + n_2 )(n_1 + n_2 -4) \implies (n_1^2-4n_1) + (n_2^2-4n_2)=0$. Since $f(x)=x^2-4x, f(2)=-4, f(1)=f(3)=-3, f(4)=0, f(5)=5$, then $n_1 = n_2 = 4$. Then $B \cap D = \{ K_{4,4} \}$.

$C \cap D$: $2n = n(n-4) \implies 2 = n-4 \implies n=m=6$, then $C \cap D = \{ C_6 \}$.

2

G1 only has cycles of length 6, while G2 and G3 only have cycles of length 5, therefore G1 is not isomorphic to G2 or G3.

G2 and G3 are isomorphic, by taking the bijective indicated by the colors shown below. Specifically, from $G_2 \to G_3$, the orange vertices stay as a $C_5$ pointing upward but shrink and the pink vertices stay as a $C_5$ pointing downward but expend, while black ones stay basically the same but rounder.

Untitled

3

  1. connected but no cycles: G is all trees with 4 vertices, which consists $P_4, K_{1,3}$.

    Untitled

  2. connected with exactly one cycle: a $C_3$ along with one extra vertex connected with one of the vertices on the cycle (paw graph $K_{1,3} + e$), and $C_4$

  3. 3-regular graph G with 5 vertices: complement graph G’ is 1-regular. However, since there’s an odd number of vertices, and G’ must consists of some pairs of vertices connecting to each other only, such graph doesn’t exist, so neither G.