← Introductory Combinatorics
第 6 章 · 20 分钟
From counting to structure: graphs and the handshake lemma
The same 'two ways' seen on a structural problem.
概念地图
Graph
Vertices and edges; counting problems become structural ones.
深色为本章概念，浅色为其他章
陪练模式
不想只是读？让它带你走一遍。
导师把这一章拆成小步，每一步先问你，再讲；你用自己的话答，它先认下对的部分再纠偏。用你自己的 AI，对话只存在这台设备上。
Locus01
延伸阅读
Euler · 1736 · the bridges of Königsberg
Stripped the geometry out of a question about city bridges, keeping only the connections, and proved an impossibility. He argued against settling it by trial walks; the cost is that the step also discards distance and direction, so any question depending on those can no longer use the model.
Foundational
Nineteenth-century graph theory · Cayley, Kirkman and others
Turned graphs from a one-off device into an object of study, handling tree counting and colouring. This made structure itself countable; the cost is that many natural questions (a chromatic number, say) have no closed form of the kind counting formulas do.
Turn
The arrival of computational complexity · later twentieth century
Proved that a family of natural graph questions (deciding three-colourability, say) is computationally hard, separating 'well defined' from 'computable' for good. A direct correction to reading 'modelled as a graph' as 'solved'.
Revision
Brualdi · the introduction to graph theory
The subject of this course. The textbook starts from definitions and the handshake lemma; this chapter says the handshake lemma is exactly chapter 3's 'two ways', with the counted objects changed to edge-endpoints.
Subject of this course
机制02
Keep only the connections
What made the seven bridges tractable was not a technique but a discard: how long each bridge is and where each island lies were dropped, leaving only who is joined to whom. The object that remains is a graph. This is chapter 1's principle on a structural problem: fix the equivalence first — two layouts with the same connections count as the same graph. The more you discard, the fewer questions remain answerable, and the ones that remain become remarkably clean.
机制A spatial layout, through keeping only its connections, becomes a structural object you can count and decide on.
可迁移性测试
Move it to service dependencies: drop the data-centre locations, the bandwidth and the protocol versions, draw only 'who calls whom', and a circular dependency becomes immediately visible. The isomorphism breaks in that how damaging a cycle is really does depend on bandwidth and timeouts — exactly the information that was discarded.
机制03
Count endpoints, not edges
The first theorem on graphs needs no technique at all, and the first formal result Euler's thread left behind is precisely it — the handshake lemma. Its place in this course's argument is specific: it is chapter 3's 'two ways' again, with the twice-counted set now the pairs '(edge, one of its endpoints)', and the derivation below spells that out.
机制The set of edge-endpoints, through being tallied once by vertex and once by edge, yields an identity.
可迁移性测试
Move it to attendance records: total attendances across all meetings equals the total meetings attended across all people — both count the pairs '(person, meeting)'. The isomorphism breaks in that a meeting may have one attendee or many, while every edge of a simple graph has exactly two endpoints, which is why the coefficient there is 2.
Derivation04
The handshake lemma and one immediate consequence
What is being proved is that the degrees sum to twice the edges, and from it that the number of odd-degree vertices is even.
The graph is finite, undirected and loopless
A hypothesis. With loops the usual convention has one contribute 2 to its vertex, or the identity must be rewritten.
The degree is the number of edges incident to
A hypothesis, and where the whole content sits: degree counts edges.
Every edge has exactly two endpoints
A hypothesis. A hypergraph allows an edge on several vertices, and the coefficient there is no longer 2.
推导 · 0 / 4
Worked derivation05
The bridges: where the impossibility comes from
Why can the seven bridges of Königsberg not all be walked exactly once in a single route?
Translate 'one continuous route' into a condition on degrees, then use the consequence of the handshake lemma.
裂缝06
The boundary of this chapter's claims
争议地形07
本书主张
Abstracting a problem into a graph reduces a tangled situation to a decidable structural question, and graph theory supplies a body of ready theorems.
另一种看法
The complexity line holds that abstraction settles 'well defined' and not 'computable'; many natural graph questions are hard, so a successful model often leaves you with nowhere to go, and worse, it makes the problem feel solved.
分歧扎在
The disagreement is rooted in whether successful modelling counts as solving, not in the mathematics. Both accept that abstraction is a necessary step; at issue is how much difficulty remains after it.
什么证据能裁决
What would settle it is performance on instances: abstract a batch of real problems into graphs and count how many can be answered within an acceptable time. A high share supports 'modelling is solving'; a majority landing in the hard class shows the abstraction only moved the difficulty.
The evidence points to 'it depends which class the problem lands in': connectivity, matching and shortest paths have efficient algorithms while colouring, cliques and Hamiltonian paths do not. What is missing is a criterion for judging in advance where a new problem will land — current practice reduces first and finds out.
Boundary and counterexample08
The 'keep only the connections' commitment as a testable specification
The modelling commitment under test: a real system's key behaviour depends only on its connections, so discarding the rest does not affect the conclusion.
Hypothesis dropped: the discarded attributes (distance, capacity, timing, type) do not affect the target conclusion
The prerequisite for a graph to represent reality; once a discarded attribute matters, the graph conclusion no longer applies.
The counterexample: two service dependency graphs with identical connections, one of which cascades and one of which does not, because their timeouts differ
Identical graphs, different behaviour, so the conclusion depended on a discarded attribute.
The observable: the target behaviour of a set of real systems with identical connections and differing discarded attributes
You need pairs of instances that are graph-isomorphic and attribute-different, or nothing can be told apart.
What counts against it: behavioural differences within isomorphic pairs exceed a pre-registered threshold
The threshold is fixed in advance on the natural variation of the behaviour.
Pre-registered failure condition: differences above threshold, or the graph-based prediction being right in at most half of the pairs
Either counts as the commitment failing.
推导 · 0 / 3
接口09
Which slot it hangs on
挂在哪个槽位The conclusion you already hold is probably 'draw a diagram and it becomes clear' — a judgement about visualisation. This chapter goes at where the effect actually comes from.
Does this chapter (a) replace 'a diagram makes things visible', or (b) constrain it: what works is what you discarded, not what you drew?
慢变量Register two slow variables: how many of your recent structure diagrams state which attributes were discarded, and how many times a conclusion actually depended on one of them. Look at the second first.
小结10
本章小结
01A graph is a deliberate discard keeping only the connections; the more you discard the fewer but cleaner the answerable questions.
02The handshake lemma is 'two ways' applied to the set of edge-endpoints and needs no technique.
03'The number of odd-degree vertices is even' follows immediately from the lemma plus parity.
04Direction, hyperedges and loops each break one hypothesis and the identity changes accordingly.
05The only step carrying observational risk is that the discarded information does not affect the conclusion.
提取练习 · 合上书，先自己答一遍。
?Is 'the degrees sum to twice the number of edges' (a) obtained by counting one set two ways or (b) a modelling commitment about reality?
?Does the bridges impossibility come from (a) searching all routes or (b) a necessary condition failing?
Forced choice11
B · Identify the tag
'The degrees of all vertices sum to twice the number of edges' — what kind of step is that?
二选一
Forced choice12
C · Locate the crack
In which situation does this framework give a confident and wrong answer?
二选一
读到这里，把它记为已读。