Problem set 2: Basics of Graph Theory
1 Seminar Problems
Count the number of distinct graphs on 4 given vertices.
Generalize the result to an arbitrary number of vertices.
Which pairs \((p,q)\) correspond to at least one \((p,q)\)-graph?
Construct a graph with the degree sequence
\[ (3,3,2,2,2,2). \]
Can a graph have the degree sequence
\[ (4,4,4,4,2)? \]
Which pairs of graphs in Figure 1 are isomorphic?

Draw all pairwise non-isomorphic connected graphs on 4 vertices.
Draw the complements of these graphs and find the self-complementary graph on 4 vertices.
Count the number of non-isomorphic trees on 6 vertices with exactly 4 pendant vertices.
Prove that every tree on \(n\) vertices without vertices of degree 2 has at least
\[ \frac{n}{2}+1 \]
pendant vertices.
Prove that every connected graph has a vertex that can be removed, together with all its incident edges, such that the resulting graph remains connected.
2 Extra Exercises
Prove that in every graph with at least 2 vertices, there exist two distinct vertices having the same degree.
Draw all pairwise non-isomorphic disconnected graphs on 5 vertices.
Prove that every self-complementary graph is connected.
Hint: Prove that either a graph or its complement is connected.
Count the number of non-isomorphic \((6,11)\)-graphs.
Count the number of non-isomorphic trees with 8 edges and exactly 3 vertices of degree 2.
Let \(G\) be a \((p,q)\)-graph.
Prove the following statements:
(a) If
\[ \delta(G)\geq \frac{n-1}{2}, \]
then \(G\) is connected.
(b) In the previous statement, it is not possible to replace
\[ \frac{n-1}{2} \]
with
\[ \left\lfloor\frac{n-1}{2}\right\rfloor. \]
Note: \(\delta(G)\) denotes the minimum degree of the vertices of \(G\).
Consider a \((100,800)\)-graph.
Is it possible that:
(a) Every vertex has degree strictly less than 16?
(b) Every vertex has degree exactly 16?