2.5. Exercises

  1. A nontrivial graph G is called irregular if no two vertices of G have the same degree. Prove that no graph is irregular.
  2. 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.
  3. Let Gn.m be a self-complementary graph, where. Prove that G contains at least one vertex of degree .
  4. Let u and v be arbitrary vertices of a connected graph G. Show that there exists a walk containing all vertices of G.
  5. Prove that if G is a graph with , then G contains a cycle.
  6. Let G be a nontrivial connected graph that is not bipartite. Show that G contains adjacent vertices u and v such that is even.
  7. Prove that „is connected to" is an equivalence relation on the vertex set of a graph.