Route endpoints: every edge contributes two connections
Count the connections at each vertex in a small undirected graph and relate their total to the number of edges.
The video could not load. Check your connection and try again, or download it directly.
Download video
Open Chinese transcript
- 这个无向图只有四条边:AB、AC、BC和CD。每条边都有两个端点。
- 先数A,连接AB和AC,所以A的连接数是2。
- B连接AB和BC,也是2;C连接AC、BC、CD,所以是3。
- D只连接CD,连接数是1。逐点相加是2加2加3加1等于8。
- 换一种数法,四条边各贡献两个端点次数,也是4乘2等于8。
- 两种计数得到同一总和,能检查是否漏边;这里只验证这张有限图。
Sources for this explanation
Logical thinking
Count each edge once at each of its two endpoints, then compare that total with the sum of the four vertex degrees.
Worked example
Four vertices are joined by edges AB, AC, BC and CD. What is the sum of the numbers of connections at all four vertices?
The degrees are 2, 2, 3 and 1, with a total of 8. This agrees with four edges contributing two endpoints each.
Try one question
Each edge contributes two, so 6.