Introductory and Algebraic Graph Theory

Math 510: Spring 2018
Thomas Zaslavsky

Information and Announcements

Index

• Writing
  • Good Writing
  • Terminology and Notation
• Diestel: Comments, Corrections, Additions
  • Supplementary Problems for Diestel ("D" Problems)
• Signed Graphs: Comments, Corrections, and Additions
  • Problems for Signed Graphs ("S" Problems)
• Godsil & Royle: Comments, Corrections, and Additions
  • Supplementary Problems for Godsil & Royle ("G" Problems)

Finiteness

In this course all graphs are finite.

Infinite graphs are remarkable (see Diestel's Chapter 8) but they are different from finite graphs, and besides, we can't use them in the algebraic part of the course.

Writing

Good Writing

Terminology and Notation

• Maximal, minimal versus maximum, minimum: They are not synonymous. In combinatorics we are often looking at partial orderings, such as sets partially ordered by containment; or graphs partially ordered by subgraphs, or induced subgraphs, or minors. We use the term "maximal" to mean an object that cannot be made into a larger one in the partial ordering while retaining the property we're interested in, but "maximum" means some number associated with it is the biggest possible.
  For example, if we look at all independent vertex sets in a graph, a maximal one cannot be increased by adding a vertex, but a maximum one has the largest possible size. A maximal set may not be maximum. (Make an example.)
  "Minimal" differs from "minimum" in a similar way.
  Examples appear in the course from time to time. Please be careful, as this is subtle technical terminology!
• A partition is a way of dividing a set into subsets. Let S be a set. A partition of S is a set of subsets of S meeting certain requirements that you know.
  The elements of a partition of S, i.e., the sets in the partition, may be called the classes of the partition. (They are the equivalence classes of the associated equivalence relation on S.) Please, please don't call them "partitions"!
  There is no such thing as a "partition of a graph".
  A bipartition of S is not exactly a partition. It is a pair {A,B} (unordered) of complementary subsets of S, allowing empty subsets (that's how it differs from a partition).
  A bipartite graph has a bipartition {A,B} of V such that no edge is within A or B. The sets A and B may be called the vertex classes or simply classes.
• A "cycle" is sometimes called a circle or circuit. (The word "cycle" also has several other meanings in graph theory.)
• Induced subgraph: Let X be a set of vertices. G[X] can also be written G:X. I like the latter (for obscure reasons).
• Set of all k-subsets of S: [S]^k is also written P_k(S) or \binom{S}{k}. I use P_k(S).
• A "bridge" is also known as an isthmus, which I prefer because a "bridge" is something else also.
• Paths that are "independent" are often called internally disjoint. I prefer that because it says exactly what it means.
• A reason to say the empty graph is not connected: We can define connected components in terms of the existence of paths between vertices. Then we can define a graph to be connected if it has exactly one connected component. The empty graph has no such components, ergo it is disconnected.
• DFS (Depth First Search) tree: explained in class.
• BFS (Breadth First Search) tree: explained in class.
• Diestel, §1.7:
  • A minor of a graph Y is a graph obtained by taking a subgraph of Y and then performing contraction on the subgraph. (Remember that doing no contraction is still a contraction of the graph.)
    A broader definition: H is a minor of Y if there is a minor of Y that is isomorphic to H.
    The notation G = MX in the book is strange. It means that X is a contraction of G. It does not mean X is a minor of G.
  • Proposition 1.7.1 says that any contraction of G can be obtained by contracting one edge at a time, instead of the more complicated definition at the top of page 19.
  • A graph H is a topological minor or topological subgraph of G if there is a subdivision of H that is isomorphic to a subgraph of G.
    The notation G = TX in the book means that G is a subdivision of X. (It can be read "G is a topological X" although that would not be perfectly correct.)
• A decomposition of a graph G is a representation G = G₁∪G₂∪···∪G_k where the edge sets E₁, E₂, ..., E_k partition the edge set E of G. If E = ∅, then k = 0; otherwise k ≥ 1.
  The vertex sets V_i can be whatever is useful; for instance, decomposing into spanning forests means all V_i = V, but decomposing into P² graphs implies each |V_i| = 3.
• Diestel, §1.9:
  • A matrix has a null space, a row space, and a column space. A linear transformation has a domain, codomain, kernel, and image. A matrix is not a linear transformation. Try not to confuse them. (A matrix can be used to represent more than one linear transformation.)
  • The cut space is often called the cocycle space.
  • These are binary spaces, i.e., over the 2-element field, F₂. There is a cycle space over any field, in particular R. Similarly, there is a cocycle space over any field. The cycle and cocycle spaces over a field are always orthogonal duals. However, they don't have the simple interpretation as edge sets that we get with the binary spaces.
  • The term "cycle" can be used for an element of the cycle space. To be precise, we call an element of the binary cycle space a binary cycle and an element of the F-cycle space (F is any field) an F-cycle. (I mention this only to justify my claim that "cycle" has multiple meanings.)
• Diestel, Ch. 6:
  • A vertex is conservative if the net inflow is 0; or one can say the total inflow equals the total outflow. People also say the vertex satisfies Kirchhoff's current law (from electricity).
  • There are several similar things called "flows", which can be confusing. Here are two ways to categorize "flows":
    1. A flow can be:
       • a circulation or cycle (a 1-cycles in homology; one reason I prefer "circle" to "cycle" for the graph "cycle"), meaning that it's conservative at every vertex; or
       • a source-to-sink flow, which means a certain vertex (s) is a source of flow and another (t) is where the flow ends up; all other vertices are conservative (but sometimes there are multiple source and sink vertices); or
       • a nowhere-zero flow/cycle, which means no edge has zero flow; also, every vertex is conservative.
    2. A flow can take values in the integers, or the reals, or an abelian group. There is some overlap, but real values tend to be in network optimization with continuous units (like coal slurry or natural gas), integer values in network optimization with discrete units (like truckloads) or in combinatorial theory, group values in theoretical work.
  • A flow satisfies Kirchhoff's voltage law if the sum of flow values around every cycle is 0. When summing around a cycle, the edges should be oriented in the same direction around the cycle.
    Kirchoff's two laws are dual, in the same way the cycle space and cut space are dual.
  • Diestel's H-flows should always be called nowhere zero. They can also properly be called nowhere-zero H-circulations (from network theory) or nowhere-zero H-cycles (i.e., 1-cycles in H-homology).

Diestel: Comments, Corrections, Additions

• Thm. 1.5.1 and Cor. 1.5.3 can be combined and supplemented to make an augmented theorem.

  Theorem 1.5.1+. Let G be a graph of order n. The following statements are equivalent.
  (1) [same as Thm. 1.5.1].
  (2) [same as Thm. 1.5.1].
  (3) [same as Thm. 1.5.1].
  (4) [same as Thm. 1.5.1].
  (5) G is connected and has n−1 edges. [Slightly stronger than Cor. 1.5.3.]
  (6) G is acyclic and has n−1 edges.

• §1.7: If you're confused by the MX and TX notation, see above, §1.7.
• Exercise 1.8: Let n₀(δ,D) := the smallest order of a graph with minimum degree δ and diameter D. A good answer to this question consists of two parts: an upper bound on n₀ and a lower bound on n₀. If the upper and lower bounds are equal, you have an exact answer. If they are close, you have a good answer.
  It is all right to ignore very small values of δ and D. If you want cover all values, that's a superior answer, but more work than it's worth unless you strongly want a complete answer.
  NEW Here is my solution.
• Lemma D1. Let x, y ∈ V(G). The union of two different paths between x and y contains a cycle.
  I proved this in class on Fri., 2/2. You can use it freely.
• Lemma D2. Let x, y ∈ V(G). Any xy-walk contains an xy-path.
  "Contains" means that by deleting some set of edges and vertices, keeping the remaining ones in the same order as in the walk, you get a path.
  I may assign this for proof. Aside from that, you can use it freely.
• "Euler's" Thm. 1.8.1 was not all proved by Euler. The hard direction is due to Hierholzer, about 150 years later. (CWCID)
• Theorem 1.8.1'. A graph G has a decomposition into cycles if and only if every vertex has even degree.
  This is a useful addition to Theorem 1.8.1 in some parts of graph theory that we won't go into in this course.
  A huge 2-volume work on math related to the Euler–Hierholzer Theorem is Eulerian Graphs and Related Topics by Herbert Fleischner, 1990. A book like this on a seemingly narrow topic that takes a broad view of the subject can be a valuable resource, but for reading you want to be selective.
• Corollary 4.2.10A. Every planar graph has a vertex with degree at most 5.
  We do the easy proof of this surprisingly valuable corollary in class.
• Exercise 5.16(ii) should read "length k". It's false for length k − 1. NEW
• The grid Gr_p (more fully, the "square grid graph") has V = [p]² = [p]×[p] and edges (i,k)(i+1,k) (horizontal) for i∈[p−1], k∈[p], and (i,k)(i,k+1) (vertical) for i∈[p], k∈[p−1].
  In other words, it looks like a square of graph paper. You need this for #4.13. (Diestel defines it on p. 322.)
• Ore's Theorem on Hamiltonian cycles. Let G be a graph of order n. If the degrees of every pair of nonadjacent vertices satisfy d(x)+d(y)≥n, then G has a Hamiltonian cycle.
  The proof is the same as that of Dirac's Theorem 10.1.1. I did this proof, adapted to Ore's theorem, in class.

Supplementary Problems for Diestel ("D" Problems)

1. Let d(u,v) denote the distance between u and v in G.
   1. Property O. For two vertices x, y, if d(x,y) is odd, then all xy-walks have odd length. Answer (and of course prove):
      1. Assume Property O holds for all vertex pairs x,y. Does that imply G is bipartite? If not, are there only a few exceptions?
      2. Assume G is bipartite. Does Property O hold for all vertex pairs?
   2. Change "odd" to "even" in Property O; that gives Property E.
      1. Assume Property E holds for all vertex pairs x,y. Does that imply G is bipartite? If not, are there only a few exceptions?
      2. Assume G is bipartite. Does Property E hold for all vertex pairs?
   3. Now assume G is connected. Assume Property O holds for a particular vertex pair {a,b}. Does that imply G is bipartite? If not, say as much as you can about the exceptions.
   4. Also assume G is connected. Assume Property E for a particular vertex pair {a,b}. Does that imply G is bipartite? If not, say as much as you can about the exceptions.
2. Prove that a subgraph of a contraction of G (that means you carry out contraction first, then take a subgraph of the resulting graph) is the same thing as a contraction of a subgraph (that means you first take a subgraph H of G, then do contraction in H).
   In other words, we could have defined a minor of G with the two operations in the reverse order.
3. Suppose G is connected and has p vertices of odd degree, where p > 0. Prove (a) p is even and (b) G has a decomposition into p/2 trails but no fewer. (There are several proofs of (b): the easy one and the others.)
4. Do the answers to Problem D1 change if we assume G is 2-connected? If they do, find the changed answers.
5. Is Lemma D1 still true if you have two different (a) walks (b) trails instead of paths?
6. Prove the first sentence ("Clearly, ...") of the proof of Proposition 3.1.3.
7. Use Diestel's Exercise 4.4 to prove that K_3,3 and the Petersen graph (Fig. 6.6.1) are nonplanar.
8. Recall that T_g is the surface composed of the sphere with g handles. (Its formal name is the orientable surface of genus g.) Euler's formula for genus g is
             n − m + f = 2 − 2g.
   Here n = |V|, m = |E|, and f = number of faces, and I'm assuming every open face is an open disk (open 2-cell). (A face with a handle entirely in it means you have the wrong surface.)
       Prove the upper bound for χ(T_g) from Euler's formula without looking up the actual upper bound (which is unnecessary, and not helpful anyhow). You can check your formula by knowing it should give 4 for T₀ and 7 for T₁ (secret hint).

Signed Graphs: Comments, Corrections, and Additions

• Be careful about the difference between switching equivalence and switching isomorphism of signed graphs.
• All negative: Don't forget that −Γ is balanced iff Γ is bipartite.
• Define positive girth g₊(Σ) and negative girth g₋(Σ) as the shortest length of a positive, resp. negative, circle. These are generalizations of girth (obviously) (via +Γ) and of even and odd girth (via −Γ). There is some discussion of signed girth in NPC.
• To define (proper) coloring of a signed graph, first define a color set: for m ≥ 0, that is
          C_m := {0, ±1, ..., ±k} for odd m = 2k+1,
          C_m := {±1, ..., ±k} for even m = 2k.
  A coloring is a function κ: V \to C_m that satisfies κ(v) ≠ σ(e)κ(w) for every edge e, where v and w are the endpoints of e (v=w if e is a loop). The chromatic number χ(Σ) is the smallest m for which a coloring exists.
• The chromatic polynomial (or we could call it the odd chromatic polynomial) is the counting function χ_Σ(2k+1) := number of m-colorings for m=2k+1 (that is, for odd m).
  The zero-free chromatic polynomial (or even chromatic polynomial) is χ_Σ^*(2k) := number of m-colorings for m=2k (that is, for even m).
  These two polynomials are not usually equal.
• Suppose X is a (simple) graph. Define a signed complete graph K_X in which the edge e is positive if it is not in X and negative if it is in X. The adjacency matrix A(K_X) is also known as the Seidel matrix of X and written S(X).
• Line graphs of signed graphs. There are several ways to do this. See below for a direct description of the switching class of the line graph Λ(Σ). See the paper MTS for a description of Λ(Σ) in terms of oriented signed graphs. Here I'll explain the connection and how they relate to what I did in class (on F 5/4).
  • In class I gave a direction to positive edges, but (at first) not to negative edges. However, then it was easiest to define the sign of an edge ef in Λ(Σ) by giving arrows to a negative edge that point from the edge to the vertex at both ends. (This is really correct. In MTS I also allow the opposite arrows on a negative edge, but for G&R, Chapter 12, we don't need that.)
  • The rule for incidences is
    • + = (arrow into vertex),
    • − = (arrow away from vertex).
  • The best rule for the sign of ef is that if e and f have a common vertex u, then the sign of ef is −(product of incidence signs), i.e.,
    • ef is − if the arrows both go towards u (or both away),
    • ef is + if one goes in and one goes out.
    • If e, f have the same endpoints, then there are two edges in Λ(Σ), one of each sign, forming a negative digon. In the reduced line graph the two edges disappear. (This is important for understanding generalized line graphs.)
  • Why is this the "best rule"?
    • This is consistent with the switching-class definition below.
    • It also means that the line graph of −Γ (any all-negative signed graph) is again all negative. This is important for comparison with Chapter 12. Specifically:
      Theorem 12.A. The line graph of −Γ is Λ(−Γ) = −L(Γ).
      (It's hard to explain briefly why the minus sign is the best choice. The plus sign doesn't work because the orientation of negative edges is a random choice.)
  • In class I gave an older, obsolete rule (sorry!), namely the opposite of the"best rule" rule just stated. You should use the best rule.
  • Matrices: Let H = H(Σ) be the incidence matrix of Σ.
    • The adjacency matrix of Σ is D(Σ) − H H^T. (The matrix H H^T is the Laplacian matrix, as in G&R §13.1.)
    • Theorem 12.B. H^T H = 2I − A(Λ(Σ)).
      This is the signed-graph analog of the usual theorem (see G&R or Diestel) that for an unsigned graph with unoriented incidence matrix B = B(Γ),
            B^T B = A(L(Γ)) + 2I.
      Why? Because in line graphs we treat an unsigned graph as all negative. Theorem 12.B then says, with H = H(−Γ), that
            H^T H = 2I − A(Λ(−Γ)).
      Two facts (easy to verify from definitions): B(Γ) = H(−Γ) and −A(Λ(−Γ)) = A(L(Γ)). With this information the two previous equations become identical.
  • Theorem 12.C (Big Theorem for Signed Line Graphs). Almost all signed graphs with greatest eigenvalue ≤ +2 are line graphs of signed graphs.
    Compare this with Lemma 11.B and Corollary 11.B.1.
  • Theorem 12.D (Little Theorem for Signed Line Graphs). Suppose you have a signed graph Σ and you construct Λ(Σ) as above, while your study partner starts from [Σ] and constructs [Λ(Σ)] as below. Then [Λ(Σ)] really is the switching class of Λ(Σ); i.e., the notation doesn't lie.
• Orientation of signed graphs.
  • Definition of orientation:
    • We orient an ordinary graph by giving a direction to each edge, indicated by signed incidences. The edge gets a + sign at one end and a − sign at the other end. This is how to orient a positive edge.
    • We orient a negative edge by giving it the same sign at both ends. It gets a + sign at both ends, or a − sign at both ends.
    • This is consistent with how we formed the (oriented) incidence matrix of a signed graph.
  • This is the best way to define the line graph, as I now explain:
    • Orientation is what we "really" do to form the line graph.
      • If edges e, f in Σ meet at vertex u, the sign of line-graph edge ef is −(product of incidence signs at u).
      • If e, f have opposite signs and two common vertices (i.e., they form a negative digon), then the line graph will have a negative digon with vertices e and f. In the adjacency matrix A(Λ(Σ)), the two signs add up to give 0 in the (e,f) element.
    • Lemma 12.E. Reversing the orientation of edge e in Σ has the effect of switching vertex e in Λ(Σ).
      This is why the line graph of Σ should be a switching class, not a signed graph, and why we can think of the switching class [Λ(Σ)] as the line graph of the switching class [Σ].

Problems for Signed Graphs ("S" Problems)

1. Find all switching isomorphism classes of signings of K₄. How many are there?
2. This problem is about how negation and deletion sets are related.
   1. Is every deletion set a negation set? Is every negation set a deletion set?
      If not, can you tell which ones are (partial answers are useful; part b might be useful)?
   2. Is every minimal deletion set a minimum deletion set? Also, the same for negation sets.
   3. Prove Harary's theorem that the deletion number equals the negation number.
3. Prove that l(Σ) = min{ |E⁻(Σ^X)| : X ⊆ V }, i.e., the smallest number of negative edges in any switching of Σ.
4. Find the frustration index and frustration number of each switching isomorphism class of signed K₄'s.
5. Prove Petersdorf's theorem that
   1. The frustration index l(−K_n) = floor((n−1)²/4).
   2. This is the maximum frustration index of any signed K_n.
   3. This maximum is attained only by the signed complete graphs (K_n,σ) in the switching class [−K_n].
   4. No incomplete signed simple graph of order n can have this large a frustration index.
6. Consider the Petersen graph P.
   1. What are the switching isomorphism classes of signings of P?
   2. What is the maximum frustration index over all signings of P?
   3. Which signings attain this value of frustration index?
7. Frustration number!
   1. How is the frustration number l₀(Σ) related to l(Σ)?
   2. What is the maximum frustration number of a signed K_n? Which signed complete graphs (K_n,σ) attain this value of l₀?
   3. Assume Σ=(K_n,σ). How is l₀(Σ) related to the structure of Σ?
   4. Now assume the underlying graph |Σ| is not necessarily complete. How is l₀(Σ) related to the structure of Σ? This question does have a definite answer, unlike the similar question for l.
8. Find the chromatic number of
   1. Σ = +K₄,
   2. Σ = −K₄,
   3. Σ = K₄ with exactly one negative edge.
   4. Is there anything interesting about how the numbers compare? (There is no wrong answer to this part.)
      (See # S11 for an interesting possible answer to this.)
9. Find the two chromatic polynomials for
   1. Σ = +K₄,
   2. Σ = −K₄,
   3. Σ = K₄ with exactly one negative edge.
   4. Do you see anything interesting in comparing the results? (There is no wrong answer to this part.)
10. How are the eigenvalues and eigenvectors of A(X) related to those of S(X) = A(K_X)? (See Seidel matrix, above.)
    1. For any graph X. Start by finding a formula connecting A(X) and S(X).
    2. For a conference graph X (where the multiplicities are equal: m_θ = m_τ).
    3. For a strongly regular graph X = SRG(n, k, λ, μ). You may find the relationship is simpler for certain choices of parameter, such as conference graphs. This part of the question is the hard part.
11. The answers to # S8 suggest that χ(K_n) − χ(K_n, σ) might be a meaningful number (there were a couple of suggestions in students' answers). Does that hold up for n > 4?
    Warning: the number of switching classes rises rapidly with n; but K₅ should be manageable (given sufficient working time) and will help to destroy or support conjectures.

Godsil & Royle: Comments, Corrections, and Additions

• The authors' own corrections page. Please check this for each chapter.
• Ch. 1 correction:
  • P. 9, line 4: Z_n should be Z_n \ 0.
  • Lemma 1.7.3: minimum valency at least 4.
• Ch. 2 correction:
  • Lemma 2.5.1: By "maximal subgroup" they mean "maximal proper subgroup". (The only maximal subgroup of G is itself.)
• Group Action Principle #1. Whenever a group G acts on a set V, assume V is nonempty. For the results on permutation groups we should assume |V| ≥ 2.
• The dihedral group D_m is the group of symmetries of a regular m-gon. It can also be described as a certain group of symmetries of Z_m, but I leave that description to you.
• Here is an improvement of Lemma 2.5.1 that has a similar proof.
  Lemma 2.5.1a. Let G be a transitive permutation group on V and let x be a point in V. There is a bijection between systems of imprimitivity of G and subgroups H such that G_x ≤ H ≤ G.
• Ch. 4 corrections:
  • The definition of s-arc transitivity of a graph X, that Aut X is transitive on s-arcs, assumes implicitly that an s-arc exists (see G.A.P. #1). We don't assume, e.g., that G is transitive on V; that assumption would have to be stated separately.
  • The statements
    • on p. 59 that "it is obvious" that s-arc transitivity implies (s−1)-arc transitivity, and
    • on p. 60 that X is s-arc transitive if and only if X is transitive and Aut X is transitive on s-arcs from a fixed vertex u (here for simplicity I let the book's group G be Aut X),
    are false without added hypotheses.
          What added hypotheses? After reviewing some literature, it seems sufficient and appropriate to assume that X is vertex transitive and has valency ≥ 3. That rules out forests (which are obvious counterexamples). It also rules out cycles, which are exceptional examples in a trivial way, as the book observes.
  • P. 67, line 2: The k-cubes are in §3.1.
• Ch. 10 comments:
  • The notation SRG(n, k, a, c) means a strongly regular graph (SRG) with the indicated parameters.
  • The parameters a and c of a strongly regular graph are usually called λ and μ in the literature. I will often call them that, possibly unintentionally.
  • See the leisurely exposition about SRG by S.S. Sane, focussed on one important example.
  • A conference matrix is a symmetric n×n matrix A with 0 diagonal and off-diagonal entries ±1 such that A² = (n−1)I.
• Ch. 11 comments:
  • The book's definition of a "two-graph" is nonstandard i.e., wrong. (As the book says, it may seem strange to have two names for the same thing; the explanation is that they made a mistake.)
    Definition: A two-graph T on vertex set V is a set of (unordered) triples of vertices such that every (unordered) quadruple of vertices contains an even number of triples of the two-graph T.
  • Lemma 11.5.A. A two-graph (as correctly defined here) is equivalent to a (graph-)switching class of graphs with vertex set V.
  • Lemma 11.5.B. A two-graph (as correctly defined here) is equivalent to a switching class of signed complete graphs with vertex set V.
  • I worked out the details of getting equiangular lines from L(K_n) and its complement. See this write-up.
• For Ch. 12 of Godsil & Royle we want Line graphs of signed graphs. Here are the basics (simplified version for switching classes; see above for a direct signed-graph method.)
  1. There are two kinds of line graph of a signed graph: the line graph, and the reduced line graph.
  2. The line graph of a signed graph Σ, written Λ(Σ), is any signed graph in a switching class [Λ(Σ)] to be defined next. The line graph of any signed graph in [Σ] is the same.
  3. We define [Λ(Σ)] by stating the underlying graph and the signs of circles. Let G be the underlying graph of Σ.
     The underlying graph of Λ(Σ) is L(G). Terminology: An essential circle in L(G) is a circle that is the line graph of a circle in G. A vertex triangle in L(G) is a triangle that arises from three edges of G that have a common vertex. We use the same terminology for Λ(Σ).
     The negative circles of Λ(Σ) are the following:
     1. The essential circles in L(G) that come from negative circles of Σ.
     2. The vertex triangles in L(G).
     3. The circles that are sums of an odd number of these as well as any number of positive essential circles.
     The positive circles of Λ(Σ) are:
     1. The essential circles in L(G) that come from positive circles of Σ.
     2. The circles that are sums of any number of positive essential circles as well as an even number of negative essential circles and vertex triangles.
     This gives the signs of all circles, thus determining the switching class[Λ(Σ)].
  4. Lemma 11.A. Suppose Σ = −G, that is, Σ is all negative. Then −L(G) ∈ [Λ(−G)].
  5. Lemma 11.B. With appropriate choice of Λ(Σ) in its switching class, the adjacency matrix A(Λ(Σ)) = − H(Σ)^T H(Σ) + 2I. [Corrected May 5.]
     Corollary 11.B.1. The greatest eigenvalue λ¹(A(Λ(Σ))) ≤ 2.
                 The least eigenvalue λ₁(A(−Λ(Σ))) ≥ −2.
  6. The reduced line graph Λ'(Σ) is obtained from Λ(Σ) by deleting negative digons, i.e., pairs of edges that are parallel but have opposite signs. This is also a switching class. (I want to put a bar over Λ but in HTML I can't.)
  7. Lemma 11.C. The adjacency matrices satisfy A(Λ(Σ)) = A(Λ'(Σ)).

Supplementary Problems for Godsil & Royle ("G" Problems)

1. Are there any values v ≥ k ≥ i ≥ 0 for which J(v, k, k−i) is isomorphic to J(v,k,i)? If so, what are they? [Addendum: Also assume v ≥ 2k.]
2. Consider the circulant graph X(Z_n, {±k}), where 0 < k < n/2. How many cycles does it have, and what are their lengths?
3. 1. Prove Lemma 2.5.1a.
   2. Deduce Lemma 2.5.1 from Lemma 2.5.1a in one or two sentences.
4. Prove that if X is 3-arc transitive with girth 4, then X is complete bipartite. [You should also assume X is connected.]
5. Suppose G is a transitive permutation group of V and π = {S₁, ..., S_k} (with k ≥ 2) is a system of imprimitivity.
   1. Prove Lemma 2.5.0. π = {S₁^g: g ∈ G}. That is, each S_i = S₁^g for some group element g.
   2. Which elements of g give S₁?
   3. If g, h give the same S_i, how are they related?
6. For convenience, label the vertices of a regular m-gon clockwise, using Z_m. The dihedral group D_m acts on the vertex set V ⇆ Z_m. Can you find any systems of imprimitivity of this action that are derived from the prime factorization of m? Assume m ≥ 3. Even if you only find one S of I for one odd value of m, that's a good partial solution; hand it in. (We did this in class for even m = 2k using the evenness. I'm looking for other S of I's.)
7. We showed that the "odd graph" J(2k+1, k, 0) is 2-arc transitive and that the Petersen graph (i.e., k = 2) is 3-arc transitive. Can you find out, for each k > 2, whether the odd graph is or is not 3-arc transitive? Solve as many values of k as you can.
8. Suppose X is a connected graph and A(X)² has a disconnected graph. Prove that X is bipartite.
9. Suppose X is a bipartite graph with adjacency matrix A(X) =
   

   	O	B
   	BT	O

   (I can't do matrices well in HTML.) And suppose an eigenvector is (x, y)^T with eigenvalue θ ≠ 0 (as on p. 178). Prove that both x and y are not zero vectors.
10. Show that the Petersen graph P is strongly regular. Find its parameters. Find its eigenvalues and their multiplicities by using the SRG formulas in Chapter 10.
11. Show that a conference matrix (defined above) has equally many +1's and −1's in each row. Or does it?
12. Prove Lemma 11.5.B (above).
13. Prove Lemma 11.A.
14. Prove Lemma 11.B.
15. Prove that a generalized line graph (signed all negative) with basic graph H is the reduced line graph of a signed graph −H with negative digons attached at certain vertices.