Graph types, subgraphs, connection models and method selection

Count unordered pairs in a complete graph

For a complete simple graph Kn on n positive integer vertices, each of the n vertices has n − 1 possible neighbours. Counting these ordered choices gives n(n − 1), but every undirected edge appears once from each endpoint. Divide by two. The argument includes K1, with zero edges

A complete simple graph has 6 vertices. Find its total number of edges

A simple graph has 6 vertices and 9 edges. Find the number of additional edges needed to make it complete

Why is the complete-graph count divided by two?

A simple graph has eight vertices and nineteen edges. How many additional edges make it complete?

The regular-graph formula

If a finite graph has n vertices all of degree r, its degree sum is nr. The handshaking lemma shows that each edge contributes two to the degree sum, so the number of edges is half that sum. This argument does not require connectedness or planarity. For a simple graph, r must be an integer between zero and n − 1; nr must be even because e is an integer

A graph has ten vertices, each of degree four. How many edges does it have?

Could a simple graph have seven vertices all of degree three?

A claimed simple graph has six vertices all of degree six. Why is an even degree sum not enough?

The two formulas are consistent

Kn is (n − 1)-regular. Substituting the degree of a complete graph into the regular-graph formula recovers the complete-graph formula. Conversely, not every regular graph is complete: a cycle on six vertices is 2-regular with six edges, while K6 has fifteen edges. The pair-count and degree-count arguments do not depend on any particular drawing

Write the two counting proofs, ungraded

Without appealing only to a few numerical examples, prove the complete-graph and regular-graph edge-count formulas. State your assumptions, what is counted, and why each edge is counted twice

Model: complete and regular edge counts

In Kn each vertex joins the other n − 1 vertices, so the number of incident vertex-edge pairs is n(n − 1). Every undirected edge has two endpoints and contributes two such pairs, giving 2e = n(n − 1). Hence the edge count is half the number of incident vertex-edge pairs. In an r-regular graph, counting the same pairs by vertices gives nr, and counting by edges gives 2e by the handshaking lemma. Thus the edge count is half the degree sum. These are universal counts under the stated hypotheses, not conclusions inferred from a list of examples