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?

Figure 1: Graphs for Problem 3

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?