Math Problems Vault

Problem 2.8.1

From every connected multigraph one can remove a vertex (together with all edges incident to it) so that it remains connected.

?

Remark.

?

A graph or multigraph is called 2-connected if it differs from $K_{2}$ and remains connected after the removal of any vertex.

Problem 2.8.2

(1)(2)

?

(1)

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.

(2)

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?

Problem 2.8.3

If a multigraph has at least one edge and, after the removal of any edge, there is still a path between the vertices $a$ and $b$ , then the multigraph contains two paths between the vertices $a$ and $b$ having no edges in common.

?

Problem 2.8.4

(1)(2)(3)

?

(1)

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.

(2)

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.)

(3)

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.

Problem 2.8.5

(1)(2)

?

(1)

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.

(2)

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.

Problem 2.8.6

Call vertices $A$ and $B$ of a graph equivalent if there exists a sequence of vertices $A = A_{0}, A_{1}, \ldots , A_{n} = B$ such that any two consecutive vertices $A_{i}$ and $A_{i+1}$ can be joined by $k$ paths having no common intermediate vertices. Then any two equivalent vertices can be joined by $k$ paths having no common edges.

?