Fundamentals of Graph Theory

Every cycle that does not pass along any edge twice contains a non-self-intersecting cycle.

Every cycle of odd length contains a non-self-intersecting cycle of odd length.

Does the analogous statement hold for cycles of even length that do not pass along any edge twice?

A graph has a non-self-intersecting cycle passing through the edges $a$ and $b$, and also a non-self-intersecting cycle passing through the edges $b$ and $c$. Then there is a non-self-intersecting cycle passing through the edges $a$ and $c$.

Every tree has a leaf, i.e., a vertex of degree 1.

Every tree with $n$ vertices has $n-1$ edges.

In every tree, between any two vertices there exists a unique non-self-intersecting path.

A sequence of $n$ positive integers is the degree sequence of some tree if and only if the sum of its terms equals $2n-2$.

those having an isolated vertex or those not having one?

connected ones or disconnected ones?

Cayley's formula. The number of trees with $n$ given vertices equals $n^{n-2}$.

If the sum of positive integers $d_{1}, \ldots , d_{n}$ equals $2n-2$, then the number of trees with $n$ given vertices in which the $i$-th vertex has degree $d_{i}$ equals $\dfrac {(n-2)!}{(d_{1}-1)! \cdot \ldots \cdot (d_{n}-1)!}$.

This statement can be reformulated as follows:

where the sum is taken over all trees $T$ with vertices $1,2,\ldots ,n$, and $\deg_{T}(k)$ denotes the degree of the vertex $k$ of the tree $T$.

Let $T_{1}, \ldots , T_{r}$ be trees whose vertex sets are pairwise disjoint. How many trees are there whose vertex set is the union of the vertex sets of these $r$ trees and which contain $T_{1}, \ldots , T_{r}$?

Find the Prüfer code of the tree with vertices $1,2,\ldots ,10$ and edges $(8,9), (8,4), (4,10), (10,3), (3,5), (10,6), (10,1), (1,7), (1,2)$.

Reconstruct the tree from the Prüfer code $1,1,2,5,4,2,7$.

The Prüfer code defines a bijection between the set of trees with $n$ given vertices and the set of words of length $n-2$ over the numbers from 1 to $n$.

In the Prüfer code, a vertex of degree $d$ occurs $d-1$ times.

Which are more numerous: trees with 100 given vertices or unicyclic graphs with 98 given vertices?

Express the number of unicyclic graphs with $n$ given vertices as a sum of at most $n$ terms.

A tree has no nonempty subgraphs in which the degree of every vertex is even and positive.

For a graph $G$, denote by $h_{1}(G)$ the number of its subgraphs without isolated vertices in which the degree of every vertex is even. (The empty subgraph satisfies this condition.) Prove that $h_{1}(G)$ is a power of two. Express $h_{1}(G)$ in terms of the number $n$ of vertices, the number $e$ of edges, and the number $k$ of connected components of the graph.

The edges of a tree are marked with the signs $+$ and $-$. It is allowed to change the signs on all edges issuing from one vertex. Then any arrangement can be obtained from any other.

For a graph $G$, denote by $h^{1}(G)$ the largest number of arrangements of the signs $+$ and $-$ on its edges such that none of them can be obtained from another by the operations described above. Prove that $h^{1}(G)$ is a power of two. Express $h^{1}(G)$ in terms of $n$, $e$, and $k$.

Prove that $h_{1}(G)$ and $h^{1}(G)$ do not change under the contraction of an edge, and deduce from this that $h_{1}(G) = h^{1}(G)$.

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

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

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

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

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

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

graphs with four vertices,

connected graphs with five vertices and five edges,

disconnected graphs with five vertices.

Is it true that the resulting face is bounded by a non-self-intersecting cycle?

Is it true that if one more vertex is removed, then all faces will again be bounded by non-self-intersecting cycles?

Suppose that in the resulting graph every vertex has degree at least 3. Is it true that any vertex of the new graph can be deleted so as to obtain a graph all of whose faces are bounded by non-self-intersecting cycles?

Euler's formula. For any connected plane graph with $f$ faces, the equality $n - e + f = 2$ holds.

(For a proof see, e.g., [R]. From now on this result may be used without proof. This formula is often written in the form $V - E + F = 2$.)

Find an analogue of Euler's formula for a plane graph with $k$ connected components.

Neither of the graphs $K_{5}$ and $K_{3,3}$ can be drawn in the plane without self-intersections.

Fig. 5. Nonplanar graphs

In the plane, $n$ points are marked. It is allowed to join some two of them by a polygonal line not passing through the other points. Two players take turns joining some two not yet joined points by a polygonal line. It is required that these polygonal lines do not self-intersect and do not intersect anywhere except at the marked points. The player who cannot make a move loses. For which $n$ does the player who moves first win with correct play?

List all connected plane graphs (up to isomorphism) in which the degrees of all vertices are equal and the ``degrees'' of all faces are equal (i.e., the boundary of each face consists of the same number of edges).

Remark. If parts (1), (2), or (3) do not work out, solve the following parts. For the definition of isomorphism see Sec. 2.3.

There are exactly 5 convex regular polyhedra (all faces are regular polygons with the same number of sides, and the degrees of all vertices are equal) (up to isomorphism of their graphs). A construction of the corresponding polyhedra must be given; it is not assumed to be known.

For any connected plane graph without loops and multiple edges having more than two vertices, $2e \geq 3f$ and $e \leq 3n - 6$.

Every plane graph has a vertex of degree at most 5.

If every vertex of a connected plane graph has degree $d$ and the boundary of every face consists of exactly $k \geq 3$ edges, then

6 colors;

5 colors;

[You won't be able to prove it anyway.]

for recognizing whether a graph is planar (here you may use Kuratowski's theorem without proof);

for drawing a graph that is known to be planar in the plane without self-intersections.

Fáry's theorem. A plane graph can be drawn in the plane without self-intersections so that all edges are line segments.

A non-convex polygon with opaque sides is given. Call a vertex $A$ visible from a point $X$ if the interior of the segment $AX$ does not intersect the boundary of the polygon. Call the kernel of the polygon the set of its interior points from which all vertices of the polygon are visible. Prove that if a point of the kernel is joined by segments to several arbitrarily chosen vertices of the original polygon (at least two, and not necessarily all of them), then the polygon splits into polygons with nonempty kernels.

$K_{5}$;

$K_{3,3}$;

$K_{6}$;

$K_{3,4}$;

$K_{7}$;

$K_{4,4}$.

$K_{5}$;

$K_{3,3}$;

$K_{6}$;

$K_{3,4}$.

with 5 colors;

with 6 colors;

with 7 colors?

directed, without multiple edges but possibly with loops?

undirected, without loops but possibly with multiple edges?

undirected, without loops and multiple edges?

undirected, with multiple edges and loops allowed?

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

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

Under what condition does a multigraph have an Eulerian path?

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

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

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

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.

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.

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.

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.

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

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

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

$n=3$, starting with 111;

$n=4$, starting with 1011;

$n=4$, ending with 1010.

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

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.

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

If a graph is connected and $2e \geq n^{2} - 3n + 6$, then it has a Hamiltonian cycle.

The Dirac--Ore theorem. A graph in which the sum of the degrees of any two non-adjacent vertices is at least $n$ has a Hamiltonian cycle.

Dirac's lemma. If $a_{0} \ldots a_{s}$ is a maximal one among the paths in the graph that pass through each of their vertices only once, $s \geq 3$ and $\deg a_{0} + \deg a_{s} > s$, then this graph has a non-self-intersecting cycle of length $s$.

If a connected graph has a non-self-intersecting cycle of length $s < n$, then this graph has a path of length $s$ passing through each of its vertices only once.

A graph in which the sum of the degrees of any two non-adjacent vertices is at least $n-1$ has a Hamiltonian path.

This graph has at least one non-self-intersecting cycle.

Denote by $v_{1}, \ldots , v_{s}$ a maximal non-self-intersecting cycle in this graph. Denote by $W$ any connected component of the graph obtained from the original graph by deleting the vertices of this non-self-intersecting cycle. Denote by $X$ the set of vertices of the non-self-intersecting cycle that are adjacent to $W$.

Then $\left|X\right| \geq k$.

The vertices $v_{i}, v_{i+1}$ do not both lie in $X$.

If $v_{i}, v_{j} \in X$, then the graph has no edge $v_{i+1} v_{j+1}$.

Is there a Hamiltonian path in the graph in Fig. 8?

Fig. 8. Does this graph have a Hamiltonian path?

Is there a Hamiltonian cycle in the graph in Fig. 9?

Fig. 9. The graph of the Grinberg polyhedron. Does it have a Hamiltonian path?

For which $n$ is there a Hamiltonian cycle in the graph whose vertices are the 3-element subsets of an $n$-element set, two subsets being joined by an edge if they intersect in exactly one element?

Every tournament has a directed Hamiltonian path.

For every $n$ there exists a tournament with $n$ vertices that has at least $n! / 2^{n}$ directed Hamiltonian paths.

If a graph contains no triangles, then $e \leq n^{2}/4$.

If $e = [n^{2}/4] + 1$, then the graph has at least $[n/2]$ triangles.

If $n = km$ and the graph contains no $(k+1)$-clique, then $2e \leq k(k-1) \times m^{2}$. (Passing to the complementary graph, we obtain that if $n = km$ and the graph contains no $(k+1)$-anticlique, then $2e \geq km(m-1)$.)

If the graph contains no $(k+1)$-anticlique, then $2e \geq km(m-1) + 2mr$, where $m := [n/k]$ and $r := k\{ n/k\}$.

If a graph contains no non-self-intersecting cycle of length 4, then $e < n^{3/2}$.

If a graph contains no subgraph $K_{3,2}$, then $e < 2n^{3/2}$.

If a graph contains no subgraph $K_{3,3}$, then $e < 2n^{5/3}$.

For any integers $s, t$, $2 \leq s \leq t$, if a graph contains no subgraph $K_{s,t}$, then $e < t n^{2-1/s}$.

$E_{n}(2) > n[\log_{2} n]/4$;

$E_{n}(2) \leq 2n^{3/2}$;

$E_{n}(3) \leq 2n^{5/3}$;

$\dfrac {(n-1)^{2}}{4} \leq E_{n}(4) \leq \dfrac {2(n+4)^{2}}{5}$.

Let $V$ be an $11^{q}$-element subset of the space $\mathbb {R}^{q}$ (for the definition of the space $\mathbb {R}^{q}$, see Ch. 7) every $10^{q}$-element subset of which contains two points $x,y$ at distance 1: $\left|x-y\right|=1$. Prove that for sufficiently large $q$ the number of unit distances between points of the set $V$ is greater than $12^{q}/2$:

Prove that under the conditions of the previous part the number $12^{q}/2$ can be replaced by $12{,}1^{q}$.

A special case of the vertex version of Menger's theorem. Any two distinct vertices of a 2-connected multigraph that are not joined by an edge lie on some non-self-intersecting cycle.

Is it true that for any path $P$ in a multigraph having at least three vertices there exists another path in the same multigraph with the same endpoints that does not intersect $P$ anywhere except at the endpoints?

For any edge $u$ of a 2-connected graph $G$ different from $K_{3}$, at least one of the graphs $G-u$ and $G/u$ is 2-connected.

For any two vertices of a convex polyhedron there exist three paths along its edges from one vertex to the other that are disjoint (everywhere except at these vertices). (Such graphs are called 3-connected.)

For a 3-connected graph $G$ with an edge $xy$ (whose vertices are $x,y$), the graph $G/xy$ is 3-connected if and only if the graph $G-x-y$ is 2-connected.

Whitney's theorem (vertex version). A multigraph remains connected after the removal of any $k-1$ vertices if and only if any two of its vertices can be joined by $k$ paths intersecting only at these two vertices.

Menger's theorem (vertex version). If vertices $a$ and $b$ of a multigraph $G$ that are not joined by an edge remain in the same connected component after the removal of any $k-1$ other vertices, then $a$ and $b$ can be joined by $k$ paths intersecting only at these two vertices.