2.5. Exercises
- A nontrivial graph G is called irregular if no two vertices of G have the same degree. Prove that no graph is irregular.
- Let n be a given positive integer, and let r and s
be nonnegative integers such that
and s is even. Show that there exists a graph G of order n having r even vertices and s odd vertices.
- Let Gn.m be a self-complementary graph, where
. Prove that G contains at least one vertex of degree
.
- Let u and v be arbitrary vertices of a connected graph G. Show that there exists a walk containing all vertices of G.
- Prove that if G is a graph with
, then G contains a cycle.
- Let G be a nontrivial connected graph that is not bipartite.
Show that G contains adjacent vertices u and v such that
is even.
- Prove that „is connected to" is an equivalence relation on the vertex set of a graph.