Classes of Graphs

• Read 1.3, pages 19-24
  • What graph do we call a path? How is it denoted?
    • What relation must there be between the order and the size in a path graph?
    • Is a graph that has this order-size relation necessarily a path graph? What about if it is a connected graph?
    • How many paths are there in the path graph of order \(n\)?
  • What graph do we call a circle? How is it denoted?
    • What relation must there be between the order and the size in a cycle graph?
    • Is a graph that has this order-size relation necessarily a cycle graph? What about if it is a connected graph?
  • What graph do we call complete? How is it denoted?
    • What relation must there be between the order and the size in a complete graph?
    • Is a graph that has this order-size relation necessarily a complete graph?
  • What is the complement of a graph? How is it denoted?
    • How many edges does the complement of a graph have?
    • Prove theorem 1.11: If \(G\) is a disconnected graph, then \(\bar G\) is connected.
    • If \(G\) is a connected graph, is it necessary that \(\bar G\) be disconnected?
    • If \(\bar G\) is connected, is it necessary that \(G\) be disconnected?
  • What graph do we call bipartite? What graph do we call complete bipartite?
    • How many complete bipartite subgraphs does the complete graph on 5 vertices have? Can you extend this to \(n\) vertices?
    • Prove or disprove: Every path graph of order at least \(2\) is bipartite.
    • When can a cycle graph be bipartite? Prove your answer.
    • Prove theorem 1.12: a nontrivial graph is bipartite if and only if it contains no odd cycles.
  • Two ways to construct new graphs from two existing graphs are the join and the cartesian product. Explain what those are and demonstrate for \(C_3\) combined with \(C_3\).
    • The join of two empty graphs has another name. What is that name?
  • Define the \(n\)-cube graphs \(Q_n\), and draw the graphs for \(n\leq 4\).
  • Practice problems: 1.24, 1.25, 1.27, 1.28
• Read 1.4, pages 26-28
  • How does a multigraph differ from a “normal” graph?
  • How does a pseudograph differ from a multigraph and from a “normal” graph?
  • What is a digraph, and how does it differ from a “normal” graph?
    • When is such a graph called oriented?
    • We can define many of the terms from graphs to this context. For instance define what a walk, path, a cycle would mean in a digraph, and what geodesic arcs would mean, and what the diameter would be.