Math Problems Vault

Problem 2.5.1

(1)(2)

How many multigraphs are there on $n$ given vertices that are

?

(1)

directed, without multiple edges but possibly with loops?

(2)

undirected, without loops but possibly with multiple edges?

Remark.

?

A multigraph (or a graph with loops and multiple edges) is a square table of nonnegative integers that is symmetric with respect to the main diagonal. The number at the intersection of the $i$ -th row and the $j$ -th column is interpreted as the number of edges (or the multiplicity of the edge) between the vertices numbered $i$ and $j$ when $i \neq j$ , and as the number of loops at the vertex numbered $i$ when $i = j$ . An edge is called multiple if its multiplicity is greater than one.

A directed multigraph (or a directed graph with loops and multiple edges) is a square table of nonnegative integers. If some cell (no matter whether diagonal or not) contains a number greater than 1, then the directed multigraph is said to have multiple edges.

Problem 2.5.2

(1)(2)

How many multigraphs are there on $n$ given vertices that have $k$ edges and are

?

(1)

undirected, without loops and multiple edges?

(2)

undirected, with multiple edges and loops allowed?

Problem 2.5.3

An Eulerian cycle (path) in a multigraph is a cycle (path) that passes along every edge of the multigraph exactly once.

?

(1)

A connected multigraph has an Eulerian cycle if and only if the degree of each of its vertices is even.

(2)

A connected multigraph has an Eulerian cycle if and only if its edge set decomposes into non-self-intersecting cycles.

(3)

Under what condition does a multigraph have an Eulerian path?

(4)

Under what condition does a directed multigraph have a directed Eulerian cycle?

(5)

For which $n$ does the graph $K_{n}$ have an Eulerian cycle?

(6)

The same for the graph $K_{m,n}$ .

Problem 2.5.4

(1)(2)(3)(4)

?

(1)

If the number of vertices of odd degree in a connected graph equals $2k$ , then its edge set can be represented as the union of $k$ paths, none of which passes along any edge twice and no two of which have common edges.

(2)

The edges of a graph in which the degree of each vertex is even can be supplied with arrows so that at each vertex the in-degree equals the out-degree.

(3)

All edges of a connected graph are colored in two colors. Each vertex has equally many edges of both colors leaving it. Then from any vertex one can reach any other one, changing the color of the edge at every step.

(4)

A connected graph drawn in the plane without self-intersections has an Eulerian cycle if and only if its faces can be properly colored in 2 colors, i.e., so that the color changes when crossing each edge.

Remark.

?

The in-degree of a vertex of a directed multigraph is the number of edges entering it (counted with multiplicity). The out-degree is defined similarly. Here a loop of multiplicity $k$ ``contributes'' $k$ both to the in-degree and to the out-degree.

Problem 2.5.5

(1)(2)(3)

A mathematician has forgotten the three-digit code of his lock. The lock opens if the three digits of the code are entered consecutively (even if other digits were entered before that). The mathematician enters one digit per second; each entered digit is appended at the end. Prove that the mathematician can open the lock within

?

(1)

29 seconds if only the digits 1, 3 and 7 can be used in the code;

(2)

1002 seconds if ten digits can be used in the code.

(3)

Formulate and prove the `` $0 < 1 < 2 < \ldots < 8 < 9$ '' rule for opening the lock within 1002 seconds.

Remark.

?

A de Bruijn sequence (d.B.s.) with parameters $n$ and $k$ is a sequence whose elements belong to a given set of $k$ elements (usually $\{ 0,1,\ldots ,k-1\}$ ), such that all of its subsequences of length $n$ are distinct and among these subsequences all $k^{n}$ possible sequences occur. (Thus the length of a d.B.s. equals $k^{n}+n-1$ .)

(An infinite periodic sequence with period $k^{n}$ , each subsequence of length $k^{n}+n-1$ of which is a d.B.s. with parameters $n$ and $k$ , is also called a d.B.s.)

Problem 2.5.6

(1)(2)(3)

Construct a de Bruijn sequence with parameters $k=2$ (``binary'') and

?

(1)

$n=3$ , starting with 111;

(2)

$n=4$ , starting with 1011;

(3)

$n=4$ , ending with 1010.

Problem 2.5.7

Consider the sequence of zeros and ones constructed by the following rules. It starts with $k$ ones. After that, we write 1 only if, when writing 0, not all subsequences of length $k$ of the new sequence are distinct. If even when writing 1 not all subsequences of length $k$ of the new sequence are distinct, then we stop writing the sequence. Prove that in this way a de Bruijn sequence is obtained.

?

Problem 2.5.8

(1)(2)(3)

A connected directed multigraph with $n$ vertices is given. The in-degree $d_{k}$ of each vertex $k$ equals its out-degree.

?

(1)

There exists a tree containing all vertices of this multigraph, all of whose edges are directed towards vertex 1.

(2)

Fix a tree $T$ from part (1). We traverse this graph (along the arrows), passing along each edge at most once. First we leave vertex 1 in an arbitrary direction. Next, suppose we have arrived at some vertex $v$ . We leave it along any edge not belonging to $T$ , if this is possible. If it is impossible, we leave it along the edge belonging to $T$ (such an edge is unique). Prove that the walk ends at vertex 1 and that the result is a directed Eulerian cycle.

(3)

The number of directed Eulerian cycles in this multigraph is a multiple of the number $(d_{1}-1)! \cdot \ldots \cdot (d_{n}-1)!$ .