-1

I am trying to prove that the number of edges of a complete graph with $x$ vertices is always $\frac{x^2-x}{2}$.

I'm having trouble figuring out this proof by induction. I've only just started doing induction proofs and I'm not entirely sure where to begin. Thank you very much!

Xander Henderson
  • 29,772
MrGameandWatch
  • 1
  • Do you mean $\frac{x(x-1)}{2}$? When $x=3$, $3^2-\frac{3}{2}$ is not an integer. – Toby Mak Feb 27 '18 at 00:32
  • I've edited your post to include the question in the body of the question, and to format the title. However, like Toby, I don't know if you meat $\frac{x^2-x}{2}$ or $x^2 - \frac{x}{2}$. Please check my work and make appropriate adjustments. – Xander Henderson Feb 27 '18 at 00:36
  • The first one, I apologize. I don't yet know how to format equations properly on this site. Thank you! – MrGameandWatch Feb 27 '18 at 00:41
  • @MrGameandWatch $\frac{x^2-x}{2}$ can be formatted as $frac{x^2-x}{2}$. Here's a tutorial (yes, it's quite messy). – Toby Mak Feb 27 '18 at 00:43

1 Answers1

3

Guide:

  • Consider base case: a singleton.

  • Assume the result hold true for $x$ vertices.

  • Think of how to construct a complete graph with $x+1$ vectices by adding a single node. Think of how many edges are needed to be added to the complte graph of $x$ vertices to form a complete graph of $x+1$ nodes. Use the induction hypothesis (number of edges of $x$ vertices plus the number of additional edges that are needed to include the additional node).

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Right, so the number of edges needed be added to the complete graph of x+1 vertices would be ((x+1)^2) - (x+1) / 2? – MrGameandWatch Feb 27 '18 at 00:43
  • Wouldn't that be the total number of edges in the complete graph with $x+1$ nodes? Perhaps working with particular example might help, let $x=2$, construct a complete graph with $2$ nodes, it is a line. Now, a third note appear, how many additional edge is needed to form a triangle? – Siong Thye Goh Feb 27 '18 at 00:50