Ch.4: Graphic matroids

Chapter 4 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 4.1. Graphic matroids 4.2. Graphs are matroids 4.3. Graph versions of matroid theorems 4.4. Duality and cocircuits in graphs 4.5. Connectivity and 2-isomorphism

81 flashcards · Mathematics · by lakesare

Part of Textbooks › Matroids: A Geometric Introduction (Gordon, McNulty) · 9 courses

1. [Graphic matroids] What does the principle "Why matroids matter" say?

   If a class of objects is a matroid, then every theorem that is true for matroids is true for this class. Every matroid theorem gives a theorem about graphs, vectors, transversals and hyperplane arrangements at no extra cost.Example: the spanning trees of a connected graph are the bases of a matroid, so (by the cryptomorphism between bases and circuits) the cycles are the circuits of a matroid, and circuit elimination becomes a theorem about cycles.

2. [Graphic matroids] What are the four classes of matroids the book studies in depth?

   Graphic matroids Edges of a graph; independent sets are the forests. Representable matroids Vectors in a vector space; independent sets are the linearly independent sets. Transversal matroids Built from matchings in bipartite graphs. Hyperplane arrangements Arrangements of hyperplanes in a vector space.

3. [Graphic matroids] Why are matroids the "right" level of generalization, according to Gordon and McNulty?

   There are many equivalent ways to axiomatize matroids, and many important classes in combinatorics and finite geometry satisfy the matroid axioms.

4. [Graphic matroids] Does every theorem that holds for the edges of a graph also hold for all matroids?

   No. The transfer is one way: matroid theorems hold for graphs, but graph theorems need not hold for non-graphic matroids. Example: in a graph, the symmetric difference of two cycles is a disjoint union of cycles; in U2,4U_{2,4}U2,4​ (circuits: all 3-subsets of {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4} ) the circuits {1,2,3}\{1,2,3\}{1,2,3} and {1,2,4}\{1,2,4\}{1,2,4} have symmetric difference {3,4}\{3,4\}{3,4} , which contains no circuit.

5. [Graphs are matroids] Theorem 4.1 Let GGG be a graph with edge set EEE , and let I\mathcal{I}I be the collection of all subsets of EEE that contain no cycle. Then … ?

   I\mathcal{I}I is the family of independent sets of a matroid on EEE , the cycle matroid M(G)M(G)M(G) . Example: for the triangle with edges a,b,ca, b, ca,b,c , I\mathcal{I}I consists of all subsets of size at most 2, so M(G)=U2,3M(G) = U_{2,3}M(G)=U2,3​ .

6. [Graphs are matroids] A matroid that is the cycle matroid M(G)M(G)M(G) of some graph GGG is called graphic.

   Example: U2,3U_{2,3}U2,3​ is graphic: it is M(C3)M(C_3)M(C3​) , the cycle matroid of a triangle.

7. [Graphs are matroids] Theorem 1.15. A tree TTT (acyclic connected graph) has nnn vertices. How many edges does TTT have?

   n−1\boldsymbol{n - 1}n−1 Example: a path on 4 vertices has 3 edges.

8. [Graphs are matroids] Why does every tree TTT with at least one edge have a leaf (a vertex of degree 1)?

   If every vertex had degree at least 2, a walk v1→v2→⋯v_1 \to v_2 \to \cdotsv1​→v2​→⋯ that never reuses the previous edge would eventually repeat a vertex, giving a cycle. TTT has finitely many vertices, so some vertex appears twice in the walk. A tree has no cycle, a contradiction.

9. [Graphs are matroids] A tree has a leaf (a vertex of degree 1).How does the induction prove that a tree with nnn vertices has n−1n - 1n−1 edges?

   Remove a leaf vvv and its edge eee : the result is a tree with n−1n - 1n−1 vertices, so it has n−2n - 2n−2 edges, and TTT has (n−2)+1=n−1(n - 2) + 1 = n - 1(n−2)+1=n−1 . Base case n=1n = 1n=1 : no edges.

10. [Graphs are matroids] A forest AAA (acyclic set of edges) has vvv vertices, eee edges and ccc components (disjoint trees). How are eee , vvv , ccc related?

    e=v−c\boldsymbol{e = v - c}e=v−c Each tree with viv_ivi​ vertices has vi−1v_i - 1vi​−1 edges; sum over the ccc trees.Example: two disjoint paths, on 3 and 2 vertices: v=5v = 5v=5 , c=2c = 2c=2 , e=2+1=3=5−2e = 2 + 1 = 3 = 5 - 2e=2+1=3=5−2 .

11. [Graphs are matroids] Independent set axioms: (I1) ∅∈I\emptyset \in \mathcal{I}∅∈I ; (I2) A⊆B∈I⇒A∈IA \subseteq B \in \mathcal{I} \Rightarrow A \in \mathcal{I}A⊆B∈I⇒A∈I ; (I3) A,B∈IA, B \in \mathcal{I}A,B∈I , ∣A∣<∣B∣|A| < |B|∣A∣<∣B∣ ⇒\Rightarrow⇒ some b∈B−Ab \in B - Ab∈B−A has A∪{b}∈IA \cup \{b\} \in \mathcal{I}A∪{b}∈I .Why do the acyclic edge sets of a graph satisfy (I1) and (I2)?

    ∅\emptyset∅ contains no cycle, and a subset of an acyclic set contains no cycle.

12. [Graphs are matroids] (I3) for graphs: AAA , BBB are forests with ∣A∣<∣B∣|A| < |B|∣A∣<∣B∣ ; find b∈Bb \in Bb∈B with A∪{b}A \cup \{b\}A∪{b} acyclic.How does the proof handle the easy case, where AAA is a tree?

    BBB meets more vertices than AAA , so some edge b∈Bb \in Bb∈B meets a vertex not met by AAA , and A∪{b}A \cup \{b\}A∪{b} is acyclic. AAA meets ∣A∣+1|A| + 1∣A∣+1 vertices. BBB is a forest with k≥1k \ge 1k≥1 components, so it meets ∣B∣+k>∣A∣+1|B| + k > |A| + 1∣B∣+k>∣A∣+1 vertices.

13. [Graphs are matroids] (I3) for graphs: AAA , BBB are forests with ∣A∣<∣B∣|A| < |B|∣A∣<∣B∣ ; find b∈Bb \in Bb∈B with A∪{b}A \cup \{b\}A∪{b} acyclic. AAA consists of trees T1,…,TcT_1, \dots, T_cT1​,…,Tc​ with e1,…,ece_1, \dots, e_ce1​,…,ec​ edges, and every edge of BBB joins two vertices met by AAA . Why does some edge of BBB join two different trees TiT_iTi​ , TjT_jTj​ ?

    Otherwise every edge of BBB lies inside one TiT_iTi​ , and BBB acyclic gives at most eie_iei​ edges of BBB in TiT_iTi​ , so ∣B∣≤e1+⋯+ec=∣A∣|B| \le e_1 + \cdots + e_c = |A|∣B∣≤e1​+⋯+ec​=∣A∣ . That contradicts ∣A∣<∣B∣|A| < |B|∣A∣<∣B∣ . An edge of BBB joining TiT_iTi​ to TjT_jTj​ can be added to AAA without creating a cycle. A forest AAA and the edge e∈Be \in Be∈B joining two of its trees.

14. [Graphs are matroids] In the cycle matroid M(G)M(G)M(G) , what is each matroid term in graph terms?

    Independent sets Edge sets of forests. Example: in the graph on vertices 1, 2, 3, 4 with edges a=12a = 12a=12 , b=23b = 23b=23 , c=13c = 13c=13 , d=34d = 34d=34 (an edge named by its endpoints): {a,b,d}\{a, b, d\}{a,b,d} . Bases Edge sets of spanning forests (spanning trees if GGG is connected). Example: {a,b,d}\{a, b, d\}{a,b,d} is a spanning tree. Circuits Edge sets of cycles. Example: {a,b,c}\{a, b, c\}{a,b,c} . Rank r(A)r(A)r(A) is the number of edges of a spanning forest of AAA . Example:…

15. [Graphs are matroids] GGG is the graph below (11 vertices, 16 edges a,…,pa, \dots, pa,…,p ). How many edges does each spanning tree of GGG have?

    10 GGG is connected with 11 vertices, so every spanning tree has 11−1=1011 - 1 = 1011−1=10 edges, and r(M(G))=10r(M(G)) = 10r(M(G))=10 .Example: B={b,c,e,f,g,k,l,m,o,p}B = \{b, c, e, f, g, k, l, m, o, p\}B={b,c,e,f,g,k,l,m,o,p} is a spanning tree.

16. [Graphs are matroids] GGG is the graph below (11 vertices, 16 edges a,…,pa, \dots, pa,…,p ). What is the rank of A={a,c,d,e,f,g,h,j,k,l,m}A = \{a, c, d, e, f, g, h, j, k, l, m\}A={a,c,d,e,f,g,h,j,k,l,m} in M(G)M(G)M(G) ?

    r(A)=8\boldsymbol{r(A) = 8}r(A)=8 AAA meets two vertex sets: {1,…,6}\{1, \dots, 6\}{1,…,6} (spanning tree {c,d,f,g,h}\{c, d, f, g, h\}{c,d,f,g,h} , 5 edges) and {7,8,9,10}\{7, 8, 9, 10\}{7,8,9,10} (spanning tree {j,k,l}\{j, k, l\}{j,k,l} , 3 edges). A largest forest in AAA has 5+3=85 + 3 = 85+3=8 edges.

17. [Graphs are matroids] GGG is the graph below (11 vertices, 16 edges a,…,pa, \dots, pa,…,p ). Which flat FΠF_\PiFΠ​ does the vertex partition Π={1,3,4,5},{2},{6},{7,8,10,11},{9}\Pi = \{1, 3, 4, 5\}, \{2\}, \{6\}, \{7, 8, 10, 11\}, \{9\}Π={1,3,4,5},{2},{6},{7,8,10,11},{9} give?

    FΠ={d,e,f,h,j,m,n,o}\boldsymbol{F_\Pi = \{d, e, f, h, j, m, n, o\}}FΠ​={d,e,f,h,j,m,n,o} Edges inside {1,3,4,5}\{1, 3, 4, 5\}{1,3,4,5} : d,e,f,hd, e, f, hd,e,f,h . Edges inside {7,8,10,11}\{7, 8, 10, 11\}{7,8,10,11} : j,m,n,oj, m, n, oj,m,n,o . Singleton blocks contribute no edges.

18. [Graphs are matroids] A vertex partition Π\PiΠ of a graph gives the edge set FΠF_\PiFΠ​ : all edges joining two vertices in the same block of Π\PiΠ .Why is FΠF_\PiFΠ​ a flat of M(G)M(G)M(G) ?

    Adding any edge not in FΠF_\PiFΠ​ increases the rank: the edge either meets a new vertex or joins two components of FΠF_\PiFΠ​ . An edge outside FΠF_\PiFΠ​ joins two different blocks, so it lies on no cycle within FΠF_\PiFΠ​ plus that edge.

19. [Graphs are matroids] Can two different vertex partitions give the same flat of M(G)M(G)M(G) ?

    Yes. Example: {1,3,4,5},{2},{6},{7,8,10,11},{9}\{1, 3, 4, 5\}, \{2\}, \{6\}, \{7, 8, 10, 11\}, \{9\}{1,3,4,5},{2},{6},{7,8,10,11},{9} and {1,3,4,5},{2,6,9},{7,8,10,11}\{1, 3, 4, 5\}, \{2, 6, 9\}, \{7, 8, 10, 11\}{1,3,4,5},{2,6,9},{7,8,10,11} both give {d,e,f,h,j,m,n,o}\{d, e, f, h, j, m, n, o\}{d,e,f,h,j,m,n,o} : no edge joins two of the vertices 2, 6, 9.

20. [Graphs are matroids] A set of edges whose removal breaks a component of a graph into two or more pieces is a cut-set; the cocircuits of M(G)M(G)M(G) are the minimal ones.

    Matroid cocircuits are also called bonds, a term from graph theory.

21. [Graphs are matroids] GGG is the graph below (11 vertices, 16 edges a,…,pa, \dots, pa,…,p ). Why is C∗={j,m,n,o}C^* = \{j, m, n, o\}C∗={j,m,n,o} a cocircuit of M(G)M(G)M(G) ?

    G−C∗G - C^*G−C∗ has exactly two components, so C∗C^*C∗ is a minimal cut-set. The components: {8,9,10}\{8, 9, 10\}{8,9,10} (edges k,lk, lk,l ) and all other vertices. Putting back any one edge of C∗C^*C∗ reconnects them. E−C∗E - C^*E−C∗ is a hyperplane.Example: {e,f,g,h}\{e, f, g, h\}{e,f,g,h} is also a cocircuit; it separates vertex 5 from the rest.

22. [Graphs are matroids] GGG is a connected graph. Why is a hyperplane HHH of M(G)M(G)M(G) the complement of a minimal cut-set?

    HHH is a maximal edge set containing no spanning tree, so E−HE - HE−H is a minimal edge set whose removal disconnects GGG .

23. [Graphs are matroids] GGG is the graph below (11 vertices, 16 edges a,…,pa, \dots, pa,…,p ). What is the closure of A={c,d,e,h,j,k,l}A = \{c, d, e, h, j, k, l\}A={c,d,e,h,j,k,l} in M(G)M(G)M(G) ?

    A‾=A∪{b,f,m}\boldsymbol{\overline{A} = A \cup \{b, f, m\}}A=A∪{b,f,m} AAA connects {1,2,3,4,5}\{1, 2, 3, 4, 5\}{1,2,3,4,5} and {7,8,9,10}\{7, 8, 9, 10\}{7,8,9,10} ; b,fb, fb,f have both ends in the first set, mmm both ends in the second. A‾\overline{A}A is the flat of the partition {1,2,3,4,5},{6},{7,8,9,10},{11}\{1, 2, 3, 4, 5\}, \{6\}, \{7, 8, 9, 10\}, \{11\}{1,2,3,4,5},{6},{7,8,9,10},{11} .

24. [Graphs are matroids] Proposition 4.3. GGG is a graph with cycle matroid M(G)M(G)M(G) . What graph G′G&#x27;G′ with M(G′)=M(G)M(G&#x27;) = M(G)M(G′)=M(G) always exists?

    A connected graph G′G&#x27;G′ . Identify one vertex of each component with a vertex of another component; this creates no new cycles and destroys none.Example: two disjoint triangles and the "bowtie" (two triangles sharing a vertex) have the same cycle matroid.

25. [Graphs are matroids] For an edge eee of a graph GGG , how are the graphs G−eG - eG−e and G/eG / eG/e formed?

    G−eG - eG−e : erase eee . G/e\ G / e G/e : erase eee and identify its two endpoints. Example: for a triangle abcabcabc , G/aG / aG/a has two vertices joined by the parallel edges bbb , ccc .

26. [Graphs are matroids] Proposition 4.4 GGG is a graph and eee an edge that is neither a loop nor an isthmus of M(G)M(G)M(G) . Then M(G)−e= ?M(G) - e = \; ?M(G)−e=? and M(G)/e= ?M(G) / e = \; ?M(G)/e=?

    M(G)−e=M(G−e)\boldsymbol{M(G) - e = M(G - e)}M(G)−e=M(G−e) and M(G)/e=M(G/e)\boldsymbol{M(G)/e = M(G/e)}M(G)/e=M(G/e) Example: triangle abcabcabc : M(G)/aM(G)/aM(G)/a has circuit {b,c}\{b, c\}{b,c} , and G/aG/aG/a has b,cb, cb,c parallel.

27. [Graphs are matroids] M(G)/e=M(G/e)M(G)/e = M(G/e)M(G)/e=M(G/e) for an edge eee that is neither a loop nor an isthmus.Why is a set III of edges independent in M(G)/eM(G)/eM(G)/e exactly when III is acyclic in G/eG/eG/e ?

    III independent in M(G)/eM(G)/eM(G)/e means I∪eI \cup eI∪e is acyclic in GGG , i.e. III contains no path joining the endpoints of eee and no cycle; that is exactly III acyclic in G/eG/eG/e . A path in III between the endpoints of eee becomes a cycle once the endpoints are identified.

28. [Graphs are matroids] In a connected graph GGG , what is an isthmus (coloop) of M(G)M(G)M(G) ?

    A cut-set of size 1: an edge whose erasure disconnects GGG . Graph theorists call it a bridge.Example: in a path, every edge is an isthmus.

29. [Graphs are matroids] GGG is the graph below (11 vertices, 16 edges a,…,pa, \dots, pa,…,p ). The edges iii and ppp are the only edges between {1,…,6}\{1, \dots, 6\}{1,…,6} and {7,…,11}\{7, \dots, 11\}{7,…,11} . Is iii a bridge (isthmus)?

    No. Erasing iii alone leaves GGG connected (through ppp ); GGG has no bridges. {i,p}\{i, p\}{i,p} is a cut-set of size 2, not two bridges. The same holds for {k,l}\{k, l\}{k,l} .

30. [Graph versions of matroid theorems] What do weak circuit elimination (C3) and strong circuit elimination (C3') say?

    Weak (C3) If C1≠C2C_1 \ne C_2C1​=C2​ are circuits and e∈C1∩C2e \in C_1 \cap C_2e∈C1​∩C2​ , there is a circuit C3⊆(C1∪C2)−eC_3 \subseteq (C_1 \cup C_2) - eC3​⊆(C1​∪C2​)−e . Strong (C3') If C1,C2C_1, C_2C1​,C2​ are circuits with x∈C1−C2x \in C_1 - C_2x∈C1​−C2​ and y∈C1∩C2y \in C_1 \cap C_2y∈C1​∩C2​ , there is a circuit C3⊆C1∪C2C_3 \subseteq C_1 \cup C_2C3​⊆C1​∪C2​ with x∈C3x \in C_3x∈C3​ and y∉C3y \notin C_3y∈/C3​ . Example: in U2,4U_{2,4}U2,4​ on {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4} , C1={1,2,3}C_1…

31. [Graph versions of matroid theorems] The set (A−B)∪(B−A)(A - B) \cup (B - A)(A−B)∪(B−A) is the symmetric difference of AAA and BBB , written A△BA \triangle BA△B .

    Example: {1,2,3}△{2,3,4}={1,4}\{1, 2, 3\} \triangle \{2, 3, 4\} = \{1, 4\}{1,2,3}△{2,3,4}={1,4} .

32. [Graph versions of matroid theorems] Theorem 4.5 C1C_1C1​ and C2C_2C2​ are circuits of the cycle matroid M(G)M(G)M(G) of a graph GGG . What is C1△C2C_1 \triangle C_2C1​△C2​ ?

    A disjoint union of circuits. Bottom: C1={a,b,c,d,p,o,l,k,j,i}C_1 = \{a, b, c, d, p, o, l, k, j, i\}C1​={a,b,c,d,p,o,l,k,j,i} and C2={f,g,i,j,n,p}C_2 = \{f, g, i, j, n, p\}C2​={f,g,i,j,n,p} . Top: C1△C2=C3∪C4C_1 \triangle C_2 = C_3 \cup C_4C1​△C2​=C3​∪C4​ with C3={a,b,c,d,f,g}C_3 = \{a, b, c, d, f, g\}C3​={a,b,c,d,f,g} , C4={k,l,o,n}C_4 = \{k, l, o, n\}C4​={k,l,o,n} .

33. [Graph versions of matroid theorems] In a graph, C1△C2C_1 \triangle C_2C1​△C2​ is a disjoint union of cycles for any two cycles C1,C2C_1, C_2C1​,C2​ .Why does this imply strong circuit elimination for M(G)M(G)M(G) ?

    Each edge x∈C1−C2x \in C_1 - C_2x∈C1​−C2​ lies in a cycle inside C1△C2C_1 \triangle C_2C1​△C2​ , which avoids every edge of C1∩C2C_1 \cap C_2C1​∩C2​ .

34. [Graph versions of matroid theorems] Claim: for cycles C1,C2C_1, C_2C1​,C2​ of a graph, every vertex has even degree in C1△C2C_1 \triangle C_2C1​△C2​ .Why is this true at a vertex vvv on both cycles?

    vvv has degree 2, 3 or 4 in C1∪C2C_1 \cup C_2C1​∪C2​ , and then degree 0, 2 or 4 in C1△C2C_1 \triangle C_2C1​△C2​ respectively. Degree 2: both edges at vvv are in C1∩C2C_1 \cap C_2C1​∩C2​ . Degree 3: exactly one edge in C1∩C2C_1 \cap C_2C1​∩C2​ . Degree 4: no edge in C1∩C2C_1 \cap C_2C1​∩C2​ . A vertex on only one cycle has degree 2. Bold: edges of C1∩C2C_1 \cap C_2C1​∩C2​ ; light: edges of C1△C2C_1 \triangle C_2C1​△C2​ .

35. [Graph versions of matroid theorems] In C1△C2C_1 \triangle C_2C1​△C2​ (for cycles C1C_1C1​ , C2C_2C2​ of a graph), every vertex has even degree.Which theorem then gives that C1△C2C_1 \triangle C_2C1​△C2​ is a disjoint union of cycles?

    Euler's theorem: if every vertex of a graph has even degree, its edges split into edge-disjoint cycles. Euler proved this in 1735, solving the Königsberg bridge problem.

36. [Graph versions of matroid theorems] Is "the symmetric difference of two circuits is a disjoint union of circuits" true for all matroids?

    No. It holds for binary matroids (representable over {0,1}\{0, 1\}{0,1} ), which include the graphic ones. Example: in U2,4U_{2,4}U2,4​ (circuits: the 3-subsets of {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4} ), {1,2,3}△{1,2,4}={3,4}\{1, 2, 3\} \triangle \{1, 2, 4\} = \{3, 4\}{1,2,3}△{1,2,4}={3,4} , an independent set.

37. [Graph versions of matroid theorems] What do weak basis exchange (B3) and strong basis exchange (B3') say?

    Weak (B3) If B1,B2B_1, B_2B1​,B2​ are bases and x∈B1−B2x \in B_1 - B_2x∈B1​−B2​ , there is y∈B2−B1y \in B_2 - B_1y∈B2​−B1​ with B1−x∪{y}B_1 - x \cup \{y\}B1​−x∪{y} a basis. Strong (B3') If B1,B2B_1, B_2B1​,B2​ are bases and x∈B1−B2x \in B_1 - B_2x∈B1​−B2​ , there is y∈B2−B1y \in B_2 - B_1y∈B2​−B1​ with both B1−x∪{y}B_1 - x \cup \{y\}B1​−x∪{y} and B2−y∪{x}B_2 - y \cup \{x\}B2​−y∪{x} bases. Example: in U2,3U_{2,3}U2,3​ on {1,2,3}\{1, 2, 3\}{1,2,3} , B1={1,2}B_1 = \{1, 2\}B1​={1,2} , B2={2,3}B_2 =…

38. [Graph versions of matroid theorems] GGG has vertices 1 (top left), 2 (top right), 3 (right), 4 (bottom right), 5 (bottom left), 6 (left); edge iii joins 2 and 5, edge jjj joins 1 and 4. T1={a,c,e,g,h}T_1 = \{a, c, e, g, h\}T1​={a,c,e,g,h} , T2={b,d,e,f,i}T_2 = \{b, d, e, f, i\}T2​={b,d,e,f,i} . For which y∈T2−T1y \in T_2 - T_1y∈T2​−T1​ is T1−a∪yT_1 - a \cup yT1​−a∪y a spanning tree?

    y=d\boldsymbol{y = d}y=d or y=i\boldsymbol{y = i}y=i T1−aT_1 - aT1​−a has components {1,5,6}\{1, 5, 6\}{1,5,6} and {2,3,4}\{2, 3, 4\}{2,3,4} . The edges joining them form the cocircuit C∗={a,d,i,j}C^* = \{a, d, i, j\}C∗={a,d,i,j} , and C∗∩T2={d,i}C^* \cap T_2 = \{d, i\}C∗∩T2​={d,i} .

39. [Graph versions of matroid theorems] GGG has vertices 1 (top left), 2 (top right), 3 (right), 4 (bottom right), 5 (bottom left), 6 (left); edge iii joins 2 and 5, edge jjj joins 1 and 4. T1={a,c,e,g,h}T_1 = \{a, c, e, g, h\}T1​={a,c,e,g,h} , T2={b,d,e,f,i}T_2 = \{b, d, e, f, i\}T2​={b,d,e,f,i} . Which yyy makes both T1−a∪yT_1 - a \cup yT1​−a∪y and T2−y∪aT_2 - y \cup aT2​−y∪a spanning trees?

    y=i\boldsymbol{y = i}y=i T2∪aT_2 \cup aT2​∪a contains the unique cycle C={a,e,f,i}C = \{a, e, f, i\}C={a,e,f,i} , so yyy must be in CCC ; and y∈C∗={a,d,i,j}y \in C^* = \{a, d, i, j\}y∈C∗={a,d,i,j} . C∩C∗={a,i}C \cap C^* = \{a, i\}C∩C∗={a,i} . y=dy = dy=d fails: T2−d∪aT_2 - d \cup aT2​−d∪a leaves vertex 4 isolated.

40. [Graph versions of matroid theorems] Proposition 4.7(1) BBB is a basis of a matroid and x∉Bx \notin Bx∈/B . What does B∪xB \cup xB∪x contain?

    A unique circuit CCC , and x∈Cx \in Cx∈C : the basic (fundamental) circuit of xxx with respect to BBB . Example: in a graph, BBB a spanning tree, xxx an edge not in BBB : CCC is xxx plus the path in BBB between the endpoints of xxx .

41. [Graph versions of matroid theorems] BBB is a basis and x∉Bx \notin Bx∈/B , so B∪xB \cup xB∪x is dependent.Why does B∪xB \cup xB∪x contain only one circuit?

    Two circuits C1≠C2C_1 \ne C_2C1​=C2​ in B∪xB \cup xB∪x both contain xxx , and circuit elimination gives a circuit C3⊆C1∪C2−x⊆BC_3 \subseteq C_1 \cup C_2 - x \subseteq BC3​⊆C1​∪C2​−x⊆B , which is impossible. Every circuit in B∪xB \cup xB∪x contains xxx , since BBB is independent.

42. [Graph versions of matroid theorems] Proposition 4.7(2) BBB is a basis of a matroid on EEE and y∈By \in By∈B . What does E−(B−y)E - (B - y)E−(B−y) contain?

    A unique cocircuit C∗C^*C∗ : the basic cocircuit of yyy with respect to BBB . It is the dual of the basic circuit statement ( E−BE - BE−B is a basis of the dual). In a graph with spanning tree BBB : C∗C^*C∗ is the set of edges joining the two components of B−yB - yB−y .

43. [Graph versions of matroid theorems] Proposition 4.8. CCC is a circuit and C∗C^*C∗ a cocircuit of a matroid MMM . Which size can ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ never have?

    ∣C∩C∗∣≠1\boldsymbol{|C \cap C^*| \ne 1}∣C∩C∗∣=1 Example: in a graph, a cycle that crosses a minimal cut-set must cross back.

44. [Graph versions of matroid theorems] Claim: a circuit CCC and a cocircuit C∗C^*C∗ never satisfy C∩C∗={x}C \cap C^* = \{x\}C∩C∗={x} .How does the proof get a contradiction?

    H=E−C∗H = E - C^*H=E−C∗ is a hyperplane and C−x⊆HC - x \subseteq HC−x⊆H , so x∈C−x‾⊆H‾=Hx \in \overline{C - x} \subseteq \overline{H} = Hx∈C−x​⊆H=H , but x∈C∗x \in C^*x∈C∗ , so x∉Hx \notin Hx∈/H . x∈C−x‾x \in \overline{C - x}x∈C−x​ because CCC is a circuit; H‾=H\overline{H} = HH=H because a hyperplane is closed.

45. [Graph versions of matroid theorems] Proposition 4.9 B1,B2B_1, B_2B1​,B2​ are bases, x∈B1−B2x \in B_1 - B_2x∈B1​−B2​ , y∈B2−B1y \in B_2 - B_1y∈B2​−B1​ . Which three conditions are equivalent?

    (1) B1−x∪{y}B_1 - x \cup \{y\}B1​−x∪{y} is a basis. (2) xxx is in the basic circuit CCC of yyy with respect to B1B_1B1​ . (3) yyy is in the cocircuit C∗=E−B1−x‾C^* = E - \overline{B_1 - x}C∗=E−B1​−x​ . Example: in the triangle abcabcabc , B1={a,b}B_1 = \{a, b\}B1​={a,b} , x=ax = ax=a , y=cy = cy=c : the basic circuit of ccc is {a,b,c}∋a\{a, b, c\} \ni a{a,b,c}∋a , the cocircuit E−{b}‾={a,c}∋cE - \overline{\{b\}} = \{a, c\} \ni cE−{b}​={a,c}∋c , and {b,c}\{b, c\}{b,c} is a basis.

46. [Graph versions of matroid theorems] B1B_1B1​ a basis, x∈B1x \in B_1x∈B1​ , y∉B1y \notin B_1y∈/B1​ , CCC the basic circuit of yyy with respect to B1B_1B1​ (the unique circuit in B1∪yB_1 \cup yB1​∪y ).Why does " B1−x∪{y}B_1 - x \cup \{y\}B1​−x∪{y} is a basis" force x∈Cx \in Cx∈C ?

    If x∉Cx \notin Cx∈/C , then C⊆B1−x∪{y}C \subseteq B_1 - x \cup \{y\}C⊆B1​−x∪{y} , so that set contains a circuit and is not a basis.

47. [Graph versions of matroid theorems] B1B_1B1​ a basis, x∈B1x \in B_1x∈B1​ , y∉B1y \notin B_1y∈/B1​ , CCC the basic circuit of yyy w.r.t. B1B_1B1​ , C∗=E−B1−x‾C^* = E - \overline{B_1 - x}C∗=E−B1​−x​ .Why does y∉C∗y \notin C^*y∈/C∗ force x∉Cx \notin Cx∈/C ?

    y∈B1−x‾y \in \overline{B_1 - x}y∈B1​−x​ , so B1−x∪yB_1 - x \cup yB1​−x∪y contains a circuit through yyy ; that circuit lies in B1∪yB_1 \cup yB1​∪y , so it is CCC , and it avoids xxx . The basic circuit is the unique circuit in B1∪yB_1 \cup yB1​∪y .

48. [Graph versions of matroid theorems] B1B_1B1​ a basis, x∈B1x \in B_1x∈B1​ , y∉B1y \notin B_1y∈/B1​ , C∗=E−B1−x‾C^* = E - \overline{B_1 - x}C∗=E−B1​−x​ .Why does " B1−x∪{y}B_1 - x \cup \{y\}B1​−x∪{y} is not a basis" force y∉C∗y \notin C^*y∈/C∗ ?

    Then r(B1−x∪y)=r(B1−x)=r(B1)−1r(B_1 - x \cup y) = r(B_1 - x) = r(B_1) - 1r(B1​−x∪y)=r(B1​−x)=r(B1​)−1 , so both sets span the same hyperplane, and y∈B1−x‾y \in \overline{B_1 - x}y∈B1​−x​ .

49. [Graph versions of matroid theorems] Strong basis exchange: for bases B1,B2B_1, B_2B1​,B2​ and x∈B1−B2x \in B_1 - B_2x∈B1​−B2​ there is y∈B2−B1y \in B_2 - B_1y∈B2​−B1​ with B1−x∪yB_1 - x \cup yB1​−x∪y and B2−y∪xB_2 - y \cup xB2​−y∪x both bases.How does the proof find yyy ?

    Take CCC = the basic circuit of xxx w.r.t. B2B_2B2​ and C∗=E−B1−x‾C^* = E - \overline{B_1 - x}C∗=E−B1​−x​ . Since x∈C∩C∗x \in C \cap C^*x∈C∩C∗ and ∣C∩C∗∣≠1|C \cap C^*| \ne 1∣C∩C∗∣=1 , pick y≠xy \ne xy=x in C∩C∗C \cap C^*C∩C∗ . y∈C∗y \in C^*y∈C∗ gives that B1−x∪yB_1 - x \cup yB1​−x∪y is a basis; y∈Cy \in Cy∈C gives that B2−y∪xB_2 - y \cup xB2​−y∪x is a basis (both by the circuit / cocircuit criterion for a single exchange).

50. [Graph versions of matroid theorems] In the proof of strong basis exchange: CCC is the basic circuit of xxx w.r.t. B2B_2B2​ , C∗=E−B1−x‾C^* = E - \overline{B_1 - x}C∗=E−B1​−x​ , and y≠xy \ne xy=x lies in C∩C∗C \cap C^*C∩C∗ .Why is y∈B2−B1y \in B_2 - B_1y∈B2​−B1​ ?

    y∈C⊆B2∪xy \in C \subseteq B_2 \cup xy∈C⊆B2​∪x and y≠xy \ne xy=x , so y∈B2y \in B_2y∈B2​ ; and y∈B1y \in B_1y∈B1​ would give y∈B1−x⊆B1−x‾y \in B_1 - x \subseteq \overline{B_1 - x}y∈B1​−x⊆B1​−x​ , contradicting y∈C∗y \in C^*y∈C∗ .

51. [Graph versions of matroid theorems] Proposition 4.11. CCC is a circuit and C∗C^*C∗ a cocircuit of a graphic matroid M(G)M(G)M(G) . What can you say about ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ ?

    ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ is even. Left: the cycle abcjabcjabcj ; right: the cocircuit achiachiachi . The dashed line splits the vertices; C∩C∗={a,c}C \cap C^* = \{a, c\}C∩C∗={a,c} .

52. [Graph versions of matroid theorems] GGG connected; the cocircuit C∗C^*C∗ of M(G)M(G)M(G) splits the vertices into SSS and TTT , and each edge of C∗C^*C∗ joins SSS to TTT .Why does every cycle CCC meet C∗C^*C∗ in an even number of edges?

    Going around CCC , each edge of C∗C^*C∗ from SSS to TTT must be matched by a different edge back from TTT to SSS , since the cycle ends where it started. A cycle with all vertices in SSS (or all in TTT ) has C∩C∗=∅C \cap C^* = \emptysetC∩C∗=∅ .

53. [Graph versions of matroid theorems] Is ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ even for a circuit CCC and a cocircuit C∗C^*C∗ of every matroid?

    No, only ∣C∩C∗∣≠1|C \cap C^*| \ne 1∣C∩C∗∣=1 holds in general. Example: in U2,4U_{2,4}U2,4​ the circuits and the cocircuits are both the 3-subsets of {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4} ; the circuit {1,2,3}\{1, 2, 3\}{1,2,3} and the cocircuit {1,2,3}\{1, 2, 3\}{1,2,3} meet in 3 elements.

54. [Duality and cocircuits in graphs] Theorem 3.27 (Whitney). GGG is a connected graph. When is the dual M(G)∗M(G)^*M(G)∗ graphic, and what is it then?

    M(G)∗M(G)^*M(G)∗ is graphic if and only if GGG is planar; then M(G)∗=M(G∗)M(G)^* = M(G^*)M(G)∗=M(G∗) , where G∗G^*G∗ is the planar dual graph. Example: M(K5)∗M(K_5)^*M(K5​)∗ is not graphic, since K5K_5K5​ is not planar.

55. [Duality and cocircuits in graphs] The duals M(G)∗M(G)^*M(G)∗ of cycle matroids are called cographic matroids.

    Example: M(K5)∗M(K_5)^*M(K5​)∗ is cographic but not graphic.

56. [Duality and cocircuits in graphs] What is the vertex cut-set Cv∗C^*_vCv∗​ of a vertex vvv ?

    The set of edges incident to vvv . If its removal leaves exactly two pieces, it is a cocircuit of M(G)M(G)M(G) .Example: in the triangle abcabcabc on vertices 1, 2, 3 with a=12a = 12a=12 , b=23b = 23b=23 , c=13c = 13c=13 : C1∗={a,c}C^*_1 = \{a, c\}C1∗​={a,c} .

57. [Duality and cocircuits in graphs] GGG is the graph below (11 vertices, 16 edges a,…,pa, \dots, pa,…,p ). With C5∗={e,f,g,h}C^*_5 = \{e, f, g, h\}C5∗​={e,f,g,h} and C6∗={a,g,i}C^*_6 = \{a, g, i\}C6∗​={a,g,i} the vertex cut-sets, what is C5∗△C6∗C^*_5 \triangle C^*_6C5∗​△C6∗​ ?

    {a,e,f,h,i}\boldsymbol{\{a, e, f, h, i\}}{a,e,f,h,i} , again a cocircuit ggg cancels. Removing these edges separates {5,6}\{5, 6\}{5,6} from the other vertices. Top to bottom: C5∗C^*_5C5∗​ , C6∗C^*_6C6∗​ , C5∗△C6∗C^*_5 \triangle C^*_6C5∗​△C6∗​ .

58. [Duality and cocircuits in graphs] GGG is the graph below (11 vertices, 16 edges a,…,pa, \dots, pa,…,p ). The cocircuit {i,n,o}\{i, n, o\}{i,n,o} separates {7,8,9,10}\{7, 8, 9, 10\}{7,8,9,10} from the rest. How do you get it from vertex cut-sets?

    C7∗△C8∗△C9∗△C10∗={i,n,o}\boldsymbol{C^*_7 \triangle C^*_8 \triangle C^*_9 \triangle C^*_{10} = \{i, n, o\}}C7∗​△C8∗​△C9∗​△C10∗​={i,n,o} The symmetric difference of several sets keeps the elements in an odd number of them: j,k,l,mj, k, l, mj,k,l,m appear twice, i,n,oi, n, oi,n,o once.The vertex cut-sets of the other seven vertices 1,…,6,111, \dots, 6, 111,…,6,11 give the same cocircuit.

59. [Duality and cocircuits in graphs] What is a cut-vertex of a graph?

    A vertex whose removal (with its incident edges) disconnects the graph. The edges at the cut-vertex vvv do not form a cocircuit (not a minimal cut-set): they split into two cocircuits.

60. [Duality and cocircuits in graphs] Theorem 4.13 GGG is a graph with no cut-vertices. What three facts hold about cut-sets and vertex cut-sets?

    (1) The symmetric difference of two minimal cut-sets is a disjoint union of minimal cut-sets. (2) Every cocircuit of M(G)M(G)M(G) (minimal cut-set) is a symmetric difference of vertex cut-sets. (3) For S⊆VS \subseteq VS⊆V , let CS∗C^*_SCS∗​ be the symmetric difference of the vertex cut-sets over SSS . Then CS∗=CV−S∗C^*_S = C^*_{V - S}CS∗​=CV−S∗​ . Graphs with no cut-vertices are called blocks. The theorem generalizes to binary matroids.

61. [Duality and cocircuits in graphs] What is the cocircuit (or bond) matroid M∗(G)M^*(G)M∗(G) of a graph GGG ?

    The matroid on the edges of GGG whose circuits are the cocircuits (minimal cut-sets) of M(G)M(G)M(G) . M∗(G)=M(G)∗M^*(G) = M(G)^*M∗(G)=M(G)∗ , the dual of the cycle matroid, because CCC is a circuit of MMM exactly when CCC is a cocircuit of M∗M^*M∗ .Example: for a triangle, the minimal cut-sets are the 2-subsets, so M∗(C3)=U1,3M^*(C_3) = U_{1,3}M∗(C3​)=U1,3​ .

62. [Duality and cocircuits in graphs] GGG has mmm vertices and nnn edges. What is the vertex–edge incidence matrix AGA_GAG​ ?

    The m×nm \times nm×n matrix with aij=1a_{ij} = 1aij​=1 if vertex iii is incident to edge jjj , and aij=0a_{ij} = 0aij​=0 otherwise. Example: triangle with a=12a = 12a=12 , b=23b = 23b=23 , c=13c = 13c=13 : AG=[101110011]A_G = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}AG​=⎣⎡​110​011​101​⎦⎤​ .

63. [Duality and cocircuits in graphs] In the incidence matrix AGA_GAG​ of a loopless graph, what do the columns and the rows add up to, and which theorem follows?

    Each column has two 1's; row iii adds up to deg⁡(i)\deg(i)deg(i) . So ∑deg⁡(v)=2⋅(number of edges)\sum \deg(v) = 2 \cdot (\text{number of edges})∑deg(v)=2⋅(number of edges) . Sum all entries of AGA_GAG​ by rows and by columns. This is sometimes called the first theorem of graph theory.

64. [Duality and cocircuits in graphs] How do you see in the incidence matrix AGA_GAG​ that {a,b,c,j}\{a, b, c, j\}{a,b,c,j} is a circuit of M(G)M(G)M(G) ?

    In the columns a,b,c,ja, b, c, ja,b,c,j , each nonzero row has exactly two 1's, and these 1's form a cycle among the rows 1, 2, 3, 4. abcj11001211003011040011\begin{array}{c|cccc} & a & b & c & j \\ \hline 1 & 1 & 0 & 0 & 1 \\ 2 & 1 & 1 & 0 & 0 \\ 3 & 0 & 1 & 1 & 0 \\ 4 & 0 & 0 & 1 & 1 \end{array}1234​a1100​b0110​c0011​j1001​​

65. [Duality and cocircuits in graphs] How do you read cocircuits of M(G)M(G)M(G) off the incidence matrix AGA_GAG​ (for GGG without cut-vertices)?

    A row gives a vertex cut-set (the columns with a 1 in that row); mod 2 sums of rows give the other cocircuits. Example: row 4 has 1's in columns c,d,h,jc, d, h, jc,d,h,j , so {c,d,h,j}\{c, d, h, j\}{c,d,h,j} is a cocircuit. Rows 4 + 5 mod 2: {c,d,h,j}△{d,e,g,i}={c,e,g,h,i,j}\{c, d, h, j\} \triangle \{d, e, g, i\} = \{c, e, g, h, i, j\}{c,d,h,j}△{d,e,g,i}={c,e,g,h,i,j} , the cut separating {4,5}\{4, 5\}{4,5} .

66. [Duality and cocircuits in graphs] What do the incidence matrices tell you about representability of M(G)M(G)M(G) and M∗(G)M^*(G)M∗(G) ?

    Both are binary: representable by 0/1 matrices with arithmetic mod 2. The columns of AGA_GAG​ over {0,1}\{0, 1\}{0,1} (mod 2) are linearly independent exactly when the edges are acyclic.

67. [Connectivity and 2-isomorphism] Does the cycle matroid M(G)M(G)M(G) determine the graph GGG up to isomorphism?

    Not always. Example: every forest with nnn edges has the same cycle matroid, the Boolean algebra BnB_nBn​ (every subset independent, every element an isthmus); a path and a star with 3 edges are both B3B_3B3​ .

68. [Connectivity and 2-isomorphism] What are vertex identification and vertex splitting?

    Identification: merge a vertex of one component with a vertex of another component into one vertex. Splitting: the reverse, at a cut-vertex. Both keep the cycles, so both keep the cycle matroid. HHH = H1H_1H1​ , H2H_2H2​ ; H′H&#x27;H′ identifies xxx with yyy , H′′H&#x27;&#x27;H′′ identifies www with zzz ; M(H)=M(H′)=M(H′′)M(H) = M(H&#x27;) = M(H&#x27;&#x27;)M(H)=M(H′)=M(H′′) .

69. [Connectivity and 2-isomorphism] What is twisting a graph about two vertices uuu and vvv whose removal disconnects it?

    Split GGG into two pieces G1G_1G1​ , G2G_2G2​ with clones u1,v1u_1, v_1u1​,v1​ and u2,v2u_2, v_2u2​,v2​ of uuu , vvv , then reattach by identifying u1u_1u1​ with v2v_2v2​ and v1v_1v1​ with u2u_2u2​ . GGG : u1=u2u_1 = u_2u1​=u2​ , v1=v2v_1 = v_2v1​=v2​ . G′G&#x27;G′ (twisted): u1=v2u_1 = v_2u1​=v2​ , v1=u2v_1 = u_2v1​=u2​ .

70. [Connectivity and 2-isomorphism] GGG glues G1G_1G1​ , G2G_2G2​ by u1=u2u_1 = u_2u1​=u2​ , v1=v2v_1 = v_2v1​=v2​ ; G′G&#x27;G′ glues them by u1=v2u_1 = v_2u1​=v2​ , v1=u2v_1 = u_2v1​=u2​ . Why is M(G)=M(G′)M(G) = M(G&#x27;)M(G)=M(G′) , and why are GGG , G′G&#x27;G′ not isomorphic?

    GGG and G′G&#x27;G′ have the same cycles; but G′G&#x27;G′ has a vertex of degree 5 and GGG has none. A cycle through both glue vertices uses a path in G1G_1G1​ and a path in G2G_2G2​ ; it stays a cycle when the second path is reversed. Example: {f,g,h,m,k}\{f, g, h, m, k\}{f,g,h,m,k} is a cycle in both. deg⁡u=3+2\deg u = 3 + 2degu=3+2 in G′G&#x27;G′ ( u1u_1u1​ has degree 3, v2v_2v2​ degree 2).

71. [Connectivity and 2-isomorphism] When are two graphs GGG , G′G&#x27;G′ 2-isomorphic?

    GGG can be transformed into G′G&#x27;G′ by a sequence of vertex identifications, vertex splittings and twistings. 2-isomorphism is an equivalence relation on graphs.Example: two disjoint triangles and the bowtie (two triangles sharing a vertex) are 2-isomorphic.

72. [Connectivity and 2-isomorphism] Proposition 4.20. GGG is 2-isomorphic to G′G&#x27;G′ . What follows about the cycle matroids?

    M(G)≅M(G′)\boldsymbol{M(G) \cong M(G&#x27;)}M(G)≅M(G′) The three operations preserve the cycles, hence the circuits of the cycle matroid.

73. [Connectivity and 2-isomorphism] Whitney's 2-isomorphism theorem (1933) GGG and G′G&#x27;G′ are graphs with no isolated vertices, and M(G)≅M(G′)M(G) \cong M(G&#x27;)M(G)≅M(G′) . Then … ?

    GGG and G′G&#x27;G′ are 2-isomorphic. So graphs with the same cycle matroid differ only by vertex identifications, splittings and twistings.

74. [Connectivity and 2-isomorphism] When is a graph GGG kkk -connected, and minimally kkk -connected?

    kkk -connected: GGG stays connected after removing any set of fewer than kkk vertices. Minimally kkk -connected: kkk -connected, not (k+1)(k+1)(k+1) -connected. Example: a graph with a cut-vertex is 1-connected but not 2-connected; 2-connected graphs are the blocks; a graph with a pair of vertices where a twist is possible is not 3-connected.Example: K4K_4K4​ is 3-connected.

75. [Connectivity and 2-isomorphism] What does Steinitz's theorem say?

    The graphs of the vertices and edges of 3-dimensional polytopes are exactly the simple, planar, 3-connected graphs. Example: K4K_4K4​ is the graph of a tetrahedron.

76. [Connectivity and 2-isomorphism] Theorem 4.23 GGG is a 3-connected graph with no loops. What does M(G)M(G)M(G) determine?

    GGG itself: GGG can be uniquely reconstructed from M(G)M(G)M(G) . If M(G)=M(H)M(G) = M(H)M(G)=M(H) and HHH has no isolated vertices, then G≅HG \cong HG≅H . It follows from Whitney's 2-isomorphism theorem, since none of the three operations applies to a loopless 3-connected graph.

77. [Connectivity and 2-isomorphism] Why does the book prove "a loopless 3-connected graph is determined by its cycle matroid" without Whitney's 2-isomorphism theorem?

    The result is often used as a lemma in the proof of Whitney's theorem, so deducing it from Whitney's theorem would be circular. The direct proof also reuses the vertex cocircuit ideas.

78. [Connectivity and 2-isomorphism] GGG is loopless and 3-connected; vvv is a vertex.Why is the hyperplane E(G−v)E(G - v)E(G−v) (the edges not incident to vvv ) connected as a matroid?

    G−vG - vG−v is 2-connected, and the cycle matroid of a 2-connected graph is connected.

79. [Connectivity and 2-isomorphism] GGG is loopless and 3-connected; HHH is a hyperplane of M(G)M(G)M(G) that is not the edge set of G−vG - vG−v for any vertex vvv .Why is HHH disconnected as a matroid?

    HHH corresponds to a vertex partition A∪BA \cup BA∪B with ∣A∣,∣B∣≥2|A|, |B| \ge 2∣A∣,∣B∣≥2 , so HHH is the direct sum of the nonempty submatroids on the edges inside AAA and inside BBB . So the connected hyperplanes of M(G)M(G)M(G) are exactly the complements of the vertex cut-sets.

80. [Connectivity and 2-isomorphism] How do you reconstruct a loopless 3-connected graph GGG from M(G)M(G)M(G) ?

    Step 1 Find all connected hyperplanes H1,…,HkH_1, \dots, H_kH1​,…,Hk​ of M(G)M(G)M(G) . Step 2 Take their complements vi=E−Hiv_i = E - H_ivi​=E−Hi​ ; these are the vertex cut-sets, one for each vertex. Step 3 Each edge xxx lies in exactly two of the viv_ivi​ (the cut-sets of its two endpoints). Step 4 Draw vertices v1,…,vkv_1, \dots, v_kv1​,…,vk​ and join viv_ivi​ , vjv_jvj​ by the edge xxx exactly when x∈vi∩vjx \in v_i \cap v_jx∈vi​∩vj​ . Example: for K4K_4K4​ the 4 connected hyperplanes are t…

81. [Connectivity and 2-isomorphism] What makes generalizing theorems from graphs to matroids hard, according to Gordon and McNulty?

    A general matroid has no real analog of a vertex. For 3-connected graphs the vertices can be recovered (as complements of the connected hyperplanes).