Undirected Graphs

Prove that the sum of the degrees of all vertices of an arbitrary undirected graph equals twice the number of edges.

Prove the "handshake" lemma: the number of odd-degree vertices in a graph is even.

The name comes from the following interpretation: among the handshakes exchanged by guests at a party, the number of people who shook hands an odd number of times is even.

List all non-isomorphic loopless undirected graphs with at most four vertices.

A bridge in a connected graph is an edge whose removal disconnects the graph. Prove that an edge is a bridge if and only if it does not belong to any simple cycle.

Prove that an undirected connected graph with $n$ vertices

Prove that in any group $V$ of six people there are either three who are pairwise acquainted or three who are pairwise unacquainted. Restate this problem in terms of graphs.

Prove that an undirected graph $\mathfrak {G}=(V, E)$ is connected if and only if for every partition $V=V_{1} \cup V_{2}$ with nonempty $V_{1}$ and $V_{2}$ there exists an edge connecting some vertex of $V_{1}$ with some vertex of $V_{2}$.

Prove that if an undirected graph has exactly two odd-degree vertices, then they are connected by a path.

Prove that in a connected undirected graph, any two simple paths of maximum length have a common vertex.

Let an undirected loopless graph $\mathfrak {G}=(V, E)$ have $k$ connected components. Prove that then

Determine the minimum number of edges that must be added to a connected graph so that it can become Eulerian or semi-Eulerian.

For geodetic surveys, a territory is triangulated: divided into triangular parts. Special markers — towers — are placed at the vertices of the triangles. Determine how many towers in total are needed for the triangulation if the territory is divided into $N$ triangles, and there are $K$ towers on its boundary.

Determine how many edges and vertices a polyhedron will have if it has $f$ faces and all of them are triangular. For which $f$ can such polyhedra exist?

Vertex elimination is the following operation on a graph. If there is a vertex $v$ of degree 2 with incident edges $(v, u)$ and $(v, w), u \neq w$, then we remove the vertex $v$ and the incident edges, and add the edge $(u, w)$ instead, Fig. 41.

Fig. 41. Elimination of vertex v.

Prove that under vertex elimination, planarity and Eulerianness of the graph do not change, while the chromatic number and Hamiltonicity may change.

For each of the five regular polyhedra, draw the planar graph formed by its vertices and edges. Determine whether this graph is Eulerian, Hamiltonian, and find its chromatic number.

Show that the presence of an Eulerian cycle and a Hamiltonian cycle in a graph are independent of each other.

Determine whether the following graph $\mathfrak {G}=(V, E)$ is Eulerian (semi-Eulerian). If $\mathfrak {G}$ is not Eulerian, remove the minimum number of edges from $\mathfrak {G}$ so that it becomes one. Construct an Eulerian cycle in the original or in the resulting graph. $V=\left\{ a, b, c, e, f, g, h, k, m, n\right\} , E=\left\{ (a, c),(a, h),(a, m),(a, k)\text{, }(b, c),(b, k),(b, f),(b, m),(c, k),(c, m),(e, f),(e, g),(f, k),(f, n),(g, m),(g, h)\text{, }(h, k),(h, m),(k, n)\right\}$.

Determine whether the following graph $\mathfrak {G}=(V, E)$ is bipartite. If $\mathfrak {G}$ is not bipartite, remove the smallest number of edges from $\mathfrak {G}$ so that $\mathfrak {G}$ becomes bipartite. $V=\left\{ a, b, c, e, f, g, h, k, m, n\right\} , E=\left\{ (a, h),(a, n),(a, k),(b, k),(b\text{, }f),(b, m),(c, k),(c, h),(e, f),(e, g),(f, a),(f, m),(g, m),(m, n)\right\}$.