Count incidences instead of guessing edges

Try

A graph records which objects are connected. A finite simple undirected graph consists of a vertex set V and edges joining distinct unordered vertex pairs, with no repeated edge. Drawing crossings are not vertices unless explicitly declared.

Predict

Predict the sum of degrees in a triangle. Each of its three vertices has degree 2, so the sum is 6 while there are only 3 edges. The degree counts incident edge endpoints, and every undirected edge supplies two.

Experiment

Draw a square with one diagonal. Label degrees 3,2,3,2 and sum them. Compare that total with twice the five edges. Erase the diagonal and track exactly which two degrees decrease. This action makes the double-counting mechanism visible.

Understand

Worked handshake proof: count incidences (v,e) for which vertex v is an endpoint of edge e. Counting by vertices gives Σdeg(v); counting by edges gives 2|E|. Therefore the degree sum is even. Removing all even-degree contributions leaves a sum of odd numbers, which is even only when their count is even.

Necessary conditions do not automatically characterize possible graphs. A degree list can have even sum yet be impossible: in a five-vertex graph, a degree-4 vertex is adjacent to every other vertex, so it cannot coexist with a degree-0 vertex.

Invalid conclusion: the diagram’s visual crossings add vertices. The graph is defined by the specified endpoints, not by accidental line intersections.

Apply

Name the graph convention before counting. In a multigraph, parallel edges count separately; a loop contributes two to undirected degree. The practice here uses simple graphs unless stated otherwise, so degree is at most |V|−1.

Continue

Depth: degree-sequence characterization, planar embeddings and extremal edge bounds require further theorems. Adjacency lists and matrices encode the same graph differently; their storage and traversal costs depend on which representation is used.