Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo

Formula Review

12.2 Graph Structures

For the Sum of Degrees Theorem, sum of the degrees=2×number of edgessum of the degrees=2×number of edges or number of edges=sum of degrees2number of edges=sum of degrees2

The number of edges in a complete graph with nn vertices is the sum of the whole numbers from 1 to n1n1, 1+2+3++(n1)1+2+3++(n1).

The number of edges in a complete graph with nn vertices is 1+2+3++(n1)=n(n1)21+2+3++(n1)=n(n1)2.

12.7 Hamilton Cycles

The number of ways to arrange nn distinct objects is n!n!.

The number of distinct Hamilton cycles in a complete graph with nn vertices is (n1)!(n1)!.

12.9 Traveling Salesperson Problem

  • In a complete graph with nn vertices, the number of distinct Hamilton cycles is (n1)!(n1)!.
  • In a complete graph with nn vertices, there are at most (n1)!2(n1)!2 different weights of Hamilton cycles.

12.10 Trees

  • The number of edges in a tree graph with nn vertices is n1n1. A connected graph with n vertices and n1n1 edges is a tree graph.
Citation/Attribution

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
Citation information

© Jul 25, 2024 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.