Ch. 1: Introduction

From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 1.1. Graphs and Graph Models 1.2. Connected Graphs 1.3. Common Classes of Graphs 1.4. Multigraphs and Digraphs

86 flashcards · Mathematics · by lakesare

Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses

1. What is a graph GGG ?

   A finite nonempty set VVV of vertices, together with a set EEE of 2-element subsets of VVV , called edges. VVV and EEE are the vertex set and edge set, also written V(G)V(G)V(G) and E(G)E(G)E(G) . Since GGG is an ordered pair of two sets, some write G=(V,E)G = (V, E)G=(V,E) .

2. Some authors use the term simple graph for what is here called a graph.

   Vertices are also called points or nodes, and edges are also called lines.

3. When are two graphs GGG and HHH equal ( G=HG = HG=H )?

   When V(G)=V(H)V(G) = V(H)V(G)=V(H) and E(G)=E(H)E(G) = E(H)E(G)=E(H) .

4. How is a graph drawn as a diagram?

   Each vertex is a point (a small circle), and each edge is a line segment or curve between its two points. The diagram itself is then also called a graph.

5. In a graph, what does uvuvuv denote, and when are uuu and vvv adjacent?

   uvuvuv (or vuvuvu ) is the edge {u,v}\{u, v\}{u,v} ; uuu and vvv are adjacent if uvuvuv is an edge.

6. What are the order and the size of a graph?

   Order: the number of vertices (usually nnn ). Size: the number of edges (usually mmm ). Since the vertex set is nonempty, every graph has order at least 1.

7. A graph with exactly one vertex is called trivial; a graph of order at least 2 is called nontrivial.

8. What is the difference between a labeled and an unlabeled graph?

   A labeled graph has names on its vertices; an unlabeled one is drawn without them, when only the structure matters. (a) labeled, with V(G)={u,v,w,x,y}V(G) = \{u, v, w, x, y\}V(G)={u,v,w,x,y} ; (b) the same structure unlabeled.

9. Ten editors form seven committees, and two committees that share a member cannot meet at the same time. How is this modelled by a graph?

   Vertices: the committees. An edge joins two committees with at least one member in common. An edge means that the two committees must not be scheduled at the same time. For the book's committees: order 7, size 13.

10. S={2,3,5,8,13,21}S = \{2, 3, 5, 8, 13, 21\}S={2,3,5,8,13,21} . The graph HHH has vertex set SSS , and ijijij is an edge if i+j∈Si + j \in Si+j∈S or ∣i−j∣∈S|i - j| \in S∣i−j∣∈S . What is the size of HHH ?

    9 The edges: {2,3},{2,5},{3,5},{3,8},{5,8},{5,13},{8,13},{8,21},{13,21}\{2,3\}, \{2,5\}, \{3,5\}, \{3,8\}, \{5,8\}, \{5,13\}, \{8,13\}, \{8,21\}, \{13,21\}{2,3},{2,5},{3,5},{3,8},{5,8},{5,13},{8,13},{8,21},{13,21} .

11. Two coins, one silver and one gold, lie on two of the four squares of a 2×22 \times 22×2 board. A configuration can be transformed into another by moving one coin horizontally or vertically to the free square next to it, or by interchanging the two coins. How many configurations are there, and into how many others can each one be transformed?

    12 configurations. One with the coins side by side can be transformed into 3 others; one with the coins diagonal into 5. 12=4⋅312 = 4 \cdot 312=4⋅3 placements. Side by side: each coin has one free square next to it, plus the interchange. Diagonal: each coin has two, plus the interchange. A side-by-side configuration and its 3 transformations.

12. What is the word graph of a set of 3-letter words?

    Vertices: the words. Two words are adjacent if one is obtained from the other by interchanging two letters or by replacing one letter. e.g. ART–RAT (interchange) and ART–ARC (replacement).

13. When is a graph GGG called a word graph?

    When GGG is the word graph of some set of 3-letter words. (a) is a word graph: it is the word graph of the words in (b).

14. Committees with common members, integers whose sum or difference lies in a set, transformable coin configurations, words, conflicting traffic lanes: what do these graph models have in common?

    A set, and a relation between pairs of its elements: the vertices are the elements and the edges join related pairs. Traffic lanes, for example, are joined when vehicles in the two lanes cannot safely enter the intersection at the same time. The graph then models the situation.

15. e=uve = uve=uv is an edge of a graph. Which terms describe how uuu , vvv and eee are related?

    uuu and vvv are joined by eee and are neighbors; uuu and eee (and vvv and eee ) are incident.

16. Distinct edges incident with a common vertex are called adjacent edges.

17. When is HHH a subgraph of GGG ( H⊆GH \subseteq GH⊆G ), and when a proper subgraph?

    Subgraph: V(H)⊆V(G)V(H) \subseteq V(G)V(H)⊆V(G) and E(H)⊆E(G)E(H) \subseteq E(G)E(H)⊆E(G) . Proper: in addition, V(H)≠V(G)V(H) \ne V(G)V(H)=V(G) or E(H)≠E(G)E(H) \ne E(G)E(H)=E(G) . One also says that GGG contains HHH .

18. A subgraph of GGG with the same vertex set as GGG is a spanning subgraph of GGG .

19. When is a subgraph FFF of GGG an induced subgraph?

    Whenever u,vu, vu,v are vertices of FFF and uvuvuv is an edge of GGG , uvuvuv is an edge of FFF too. FFF keeps every edge of GGG between its own vertices.

20. For a nonempty set SSS of vertices of GGG , what is G[S]G[S]G[S] , the subgraph induced by SSS ?

    The subgraph with vertex set SSS and all edges of GGG joining two vertices of SSS . Also written ⟨S⟩G\langle S \rangle_G⟨S⟩G​ .

21. For a nonempty set XXX of edges of GGG , what is the edge-induced subgraph G[X]G[X]G[X] ?

    The subgraph with edge set XXX and all vertices incident with at least one edge of XXX . Also written ⟨X⟩G\langle X \rangle_G⟨X⟩G​ .

22. For an edge eee (or a set XXX of edges) of GGG , what is G−eG - eG−e (or G−XG - XG−X )?

    The spanning subgraph of GGG with all edges except eee (except those in XXX ). For X={e1,…,ek}X = \{e_1, \dots, e_k\}X={e1​,…,ek​} one also writes G−e1−⋯−ekG - e_1 - \dots - e_kG−e1​−⋯−ek​ .

23. For a vertex vvv (or a proper subset UUU of vertices) of GGG , what is G−vG - vG−v (or G−UG - UG−U )?

    Remove vvv (the vertices of UUU ) and every edge incident with a removed vertex. G−UG - UG−U is the induced subgraph G[V(G)−U]G[V(G) - U]G[V(G)−U] .

24. uuu and vvv are nonadjacent vertices of GGG . What is G+eG + eG+e for e=uve = uve=uv ?

    The graph with vertex set V(G)V(G)V(G) and edge set E(G)∪{e}E(G) \cup \{e\}E(G)∪{e} . So GGG is a spanning subgraph of G+eG + eG+e .

25. Which of HHH , FFF , F′F'F′ and G−eG - eG−e are induced subgraphs of GGG , and which are spanning?

    Induced: FFF . Spanning: G−eG - eG−e . Not induced: HHH and F′F'F′ lack the edge vxvxvx of GGG , and G−eG - eG−e lacks eee . F=G−{u,y}F = G - \{u, y\}F=G−{u,y} , and F′=G[{e,e′}]F' = G[\{e, e'\}]F′=G[{e,e′}] is edge-induced.

26. What is a uuu – vvv walk in a graph GGG ?

    A sequence of vertices (u=v0,v1,…,vk=v)(u = v_0, v_1, \dots, v_k = v)(u=v0​,v1​,…,vk​=v) , k≥0k \ge 0k≥0 , in which consecutive vertices are adjacent. Vertices and edges may repeat, and u=vu = vu=v is allowed. The vertices viv_ivi​ and edges vivi+1v_iv_{i+1}vi​vi+1​ lie on the walk.

27. When is a walk closed or open, and what is its length?

    Closed: it starts and ends at the same vertex; open: it doesn't. Length: the number of edges traversed, counting repeats. (u=v0,…,vk=v)(u = v_0, \dots, v_k = v)(u=v0​,…,vk​=v) has length kkk , one less than the number of listed vertices. A walk of length 0, such as (v)(v)(v) , is a trivial walk.

28. What is a uuu – vvv trail, and what is a uuu – vvv path?

    Trail: a uuu – vvv walk with no repeated edge. Path: a uuu – vvv walk with no repeated vertex. A trail may repeat vertices. Every path is a trail, since a repeated edge would repeat its end vertices.

29. Walk, trail or path: (x,y,w,y,v,w)(x, y, w, y, v, w)(x,y,w,y,v,w) , (u,w,y,x,w,v)\ (u, w, y, x, w, v) (u,w,y,x,w,v) , (u,w,y,v)\ (u, w, y, v) (u,w,y,v) ?

    Walk only; trail but not a path; path. The first repeats the edge wywywy , the second repeats the vertex www but no edge.

30. Theorem 1.6 If a graph GGG contains a uuu – vvv walk of length lll , then … ?

    GGG contains a uuu – vvv path of length at most lll .

31. If a graph contains a uuu – vvv walk of length lll , then it contains a uuu – vvv path of length at most lll .What is the key idea of the proof?

    Take a shortest uuu – vvv walk. If it repeated a vertex, ui=uju_i = u_jui​=uj​ with i<ji < ji<j , deleting ui+1,…,uju_{i+1}, \dots, u_jui+1​,…,uj​ would give a shorter uuu – vvv walk. So a shortest walk repeats no vertex: it is a path, of length at most lll .

32. What is a circuit, and what is a cycle?

    Circuit: a closed trail of length at least 3. Cycle: a circuit that repeats no vertex except the first and last. A circuit may start at any of its vertices, keeping the cyclic order. e.g. (y,w,u,v,w,x,y)(y, w, u, v, w, x, y)(y,w,u,v,w,x,y) is a circuit but not a cycle, as www repeats.

33. A cycle of length 3 is also called a triangle.

    A cycle of length kkk is a kkk -cycle; cycles of odd or even length are odd or even cycles.

34. What do you get by deleting a vertex of a cycle? Is the same true for a circuit?

    A path. For a circuit, not necessarily. e.g. the circuit (y,w,u,v,w,x,y)(y, w, u, v, w, x, y)(y,w,u,v,w,x,y) repeats www ; deleting www leaves the edges uvuvuv and xyxyxy , two separate pieces.

35. Besides a way of traversing a graph, what else do the words trail, path, circuit and cycle describe?

    The subgraph formed by the vertices and edges traversed. G1,G2,G3,G4G_1, G_2, G_3, G_4G1​,G2​,G3​,G4​ : a trail, a path, a circuit and a cycle of GGG .

36. When are two vertices uuu and vvv of a graph connected? Does that mean they are joined by an edge?

    When the graph contains a uuu – vvv path. No, adjacency is not required. Adjacent vertices are connected, though.

37. When is a graph GGG connected?

    When every two vertices of GGG are connected, i.e. there is a uuu – vvv path for every pair u,vu, vu,v . Equivalently, a uuu – vvv walk for every pair, since every walk contains a path. The trivial graph is connected.

38. What is a component of a graph GGG , and what does k(G)k(G)k(G) denote?

    A connected subgraph of GGG that is not a proper subgraph of any other connected subgraph of GGG . k(G)k(G)k(G) is the number of components. GGG is connected if and only if k(G)=1k(G) = 1k(G)=1 ; a graph that is not connected is disconnected. k(H)=3k(H) = 3k(H)=3 .

39. G1,…,GkG_1, \dots, G_kG1​,…,Gk​ are subgraphs of GGG with mutually disjoint vertex sets. When is G=G1∪⋯∪GkG = G_1 \cup \dots \cup G_kG=G1​∪⋯∪Gk​ , the union of G1,…,GkG_1, \dots, G_kG1​,…,Gk​ ?

    When every vertex and every edge of GGG belongs to exactly one of G1,…,GkG_1, \dots, G_kG1​,…,Gk​ . Every graph is the union of its components.

40. Theorem 1.7. On the vertex set of a graph GGG , let uRvu \mathrel{R} vuRv mean that uuu is connected to vvv ( GGG contains a uuu – vvv path). What kind of relation is RRR , and why?

    An equivalence relation. Reflexive and symmetric are immediate. Transitive: a uuu – vvv path followed by a vvv – www path is a uuu – www walk, and every walk contains a path.

41. How do components relate to the relation " uuu is connected to vvv " on the vertices of a graph?

    The components are the subgraphs induced by its equivalence classes. So each vertex and each edge belongs to exactly one component, and vertices in different components are never adjacent.

42. Theorem 1.8 Let GGG be a graph of order 3 or more. Which condition on two distinct vertices u,vu, vu,v of GGG makes GGG connected?

    G−uG - uG−u and G−vG - vG−v are both connected.

43. If a graph GGG of order at least 3 has distinct vertices u,vu, vu,v with G−uG - uG−u and G−vG - vG−v connected, then GGG is connected.How does the proof connect two vertices x,yx, yx,y ?

    If u∉{x,y}u \notin \{x, y\}u∈/{x,y} , they are connected in G−uG - uG−u (similarly for vvv ). If {x,y}={u,v}\{x, y\} = \{u, v\}{x,y}={u,v} , use a third vertex www : a uuu – www path in G−vG - vG−v followed by a www – vvv path in G−uG - uG−u . That uuu – vvv walk contains a uuu – vvv path.

44. If a graph GGG of order at least 3 has distinct vertices u,vu, vu,v with G−uG - uG−u and G−vG - vG−v connected, then GGG is connected.Why is "order at least 3" needed?

    Two vertices u,vu, vu,v and no edge: G−uG - uG−u and G−vG - vG−v are trivial, hence connected, yet GGG is disconnected. The proof needs a third vertex to route a uuu – vvv walk through.

45. In a connected graph GGG , what is the distance d(u,v)d(u, v)d(u,v) between vertices uuu and vvv ?

    The smallest length of a uuu – vvv path in GGG . Also written dG(u,v)d_G(u, v)dG​(u,v) . d(u,u)=0d(u, u) = 0d(u,u)=0 , and d(u,v)=1d(u, v) = 1d(u,v)=1 exactly when uvuvuv is an edge. In a disconnected graph some distances are undefined.

46. GGG is a connected graph of order nnn , and u,vu, vu,v any two vertices (distinct or not). Complete: ?≤d(u,v)≤ ?? \le d(u, v) \le \; ??≤d(u,v)≤?

    0≤d(u,v)≤n−1\boldsymbol{0} \le d(u, v) \le \boldsymbol{n - 1}0≤d(u,v)≤n−1 A path has at most nnn vertices, so at most n−1n - 1n−1 edges.

47. What is a uuu – vvv geodesic?

    A uuu – vvv path of length d(u,v)d(u, v)d(u,v) , i.e. a shortest uuu – vvv path. If (u=v0,v1,…,vk=v)(u = v_0, v_1, \dots, v_k = v)(u=v0​,v1​,…,vk​=v) is a uuu – vvv geodesic, then d(u,vi)=id(u, v_i) = id(u,vi​)=i for every iii .

48. A connected graph is drawn in levels by distance from a vertex ttt : ttt on top, its neighbors one level down, then the vertices at distance 2, and so on. Where can the two ends of an edge lie?

    In the same level or in neighboring levels. Distances from ttt of two adjacent vertices differ by at most 1.

49. What is the diameter diam⁡(G)\operatorname{diam}(G)diam(G) of a connected graph GGG ?

    The greatest distance between two vertices of GGG . diam⁡(H)=3\operatorname{diam}(H) = 3diam(H)=3 , e.g. via the yyy – sss geodesic (y,u,r,s)(y, u, r, s)(y,u,r,s) .

50. In a connected graph GGG , d(u,v)=diam⁡(G)d(u, v) = \operatorname{diam}(G)d(u,v)=diam(G) (the greatest distance between two vertices) and w≠u,vw \ne u, vw=u,v . Why can no uuu – www geodesic contain vvv ?

    Then d(u,w)>d(u,v)=diam⁡(G)d(u, w) > d(u, v) = \operatorname{diam}(G)d(u,w)>d(u,v)=diam(G) , which is impossible. On a uuu – www geodesic through vvv , d(u,w)=d(u,v)+d(v,w)d(u, w) = d(u, v) + d(v, w)d(u,w)=d(u,v)+d(v,w) , and d(v,w)≥1d(v, w) \ge 1d(v,w)≥1 .

51. Theorem 1.9 If GGG is a connected graph of order 3 or more, then GGG contains … ?

    Two distinct vertices uuu and vvv such that G−uG - uG−u and G−vG - vG−v are connected. True also for order 2.

52. Every connected graph GGG of order at least 3 has distinct vertices u,vu, vu,v with G−uG - uG−u and G−vG - vG−v connected.Which u,vu, vu,v does the proof take, and why is G−vG - vG−v connected?

    u,vu, vu,v with d(u,v)=diam⁡(G)d(u, v) = \operatorname{diam}(G)d(u,v)=diam(G) (the greatest distance). For x,yx, yx,y in G−vG - vG−v , an xxx – uuu geodesic of GGG followed by a uuu – yyy geodesic of GGG avoids vvv , so it is an xxx – yyy walk in G−vG - vG−v . A geodesic from uuu that passed through vvv would end farther from uuu than diam⁡(G)\operatorname{diam}(G)diam(G) . By symmetry G−uG - uG−u is connected too.

53. What is the difference between a necessary and a sufficient condition for a graph to be connected?

    Necessary: every connected graph has it. Sufficient: every graph that has it is connected. e.g. for order ≥3\ge 3≥3 : "two distinct vertices u,vu, vu,v with G−uG - uG−u and G−vG - vG−v connected" is both.

54. Theorem 1.10. Let GGG be a graph of order 3 or more. Complete: GGG is connected if and only if … ?

    GGG contains two distinct vertices uuu and vvv such that G−uG - uG−u and G−vG - vG−v are connected.

55. When is a graph of order nnn a path PnP_nPn​ , and when (for n≥3n \ge 3n≥3 ) a cycle CnC_nCn​ ?

    Path: its vertices can be labeled v1,…,vnv_1, \dots, v_nv1​,…,vn​ so that the edges are v1v2,v2v3,…,vn−1vnv_1v_2, v_2v_3, \dots, v_{n-1}v_nv1​v2​,v2​v3​,…,vn−1​vn​ . Cycle: the same edges plus v1vnv_1v_nv1​vn​ .

56. What is the complete graph KnK_nKn​ , and what is its size?

    The graph of order nnn in which every two distinct vertices are adjacent. Size: (n2)=n(n−1)2\boldsymbol{\binom{n}{2} = \frac{n(n-1)}{2}}(2n​)=2n(n−1)​ . The maximum size for nnn vertices. K3,K4,K5K_3, K_4, K_5K3​,K4​,K5​ have 3, 6 and 10 edges. P1=K1P_1 = K_1P1​=K1​ , P2=K2P_2 = K_2P2​=K2​ , C3=K3C_3 = K_3C3​=K3​ .

57. In a drawing of a graph, where must the vertices go, and are points where edges cross vertices?

    Anywhere convenient; and no, crossings are not vertices. Several drawings of P4P_4P4​ and of K4K_4K4​ .

58. How is this disconnected graph written?

    2K4∪C5∪P3\boldsymbol{2K_4 \cup C_5 \cup P_3}2K4​∪C5​∪P3​ Two components are K4K_4K4​ , one is C5C_5C5​ , one is P3P_3P3​ .

59. What is the complement G‾\overline{G}G of a graph GGG ?

    The graph with vertex set V(G)V(G)V(G) in which distinct u,vu, vu,v are adjacent if and only if they are not adjacent in GGG .

60. GGG has order nnn and size mmm . What are the order and size of its complement G‾\overline{G}G ?

    Order nnn , size (n2)−m\binom{n}{2} - m(2n​)−m . GGG and G‾\overline{G}G together have every pair of distinct vertices as an edge exactly once.

61. What is the empty graph of order nnn ?

    Kn‾\boldsymbol{\overline{K_n}}Kn​​ : nnn vertices and no edges. For any graph GGG of order nnn , G−E(G)=Kn‾G - E(G) = \overline{K_n}G−E(G)=Kn​​ . A graph can have an empty edge set, never an empty vertex set.

62. Theorem 1.11. If GGG is a disconnected graph, what can you say about its complement G‾\overline{G}G ?

    G‾\overline{G}G is connected. So of a graph and its complement, at least one is connected.

63. If GGG is disconnected, then its complement G‾\overline{G}G is connected.How does the proof connect two vertices u,vu, vu,v in G‾\overline{G}G ?

    Different components of GGG : uvuvuv is an edge of G‾\overline{G}G . Same component: take www in another component; (u,w,v)(u, w, v)(u,w,v) is a path in G‾\overline{G}G . Vertices in different components of GGG are never adjacent in GGG .

64. When is a graph bipartite, and what are its partite sets?

    V(G)V(G)V(G) can be partitioned into two sets UUU and WWW , the partite sets, so that every edge joins a vertex of UUU and a vertex of WWW . Left: as given. Right: redrawn with the partite sets as rows.

65. A graph is bipartite if and only if each of its components is bipartite.

66. Why is the 5-cycle C5C_5C5​ not bipartite?

    The partite sets would have to alternate around the cycle: v1∈Uv_1 \in Uv1​∈U , v2∈Wv_2 \in Wv2​∈W , v3∈Uv_3 \in Uv3​∈U , v4∈Wv_4 \in Wv4​∈W , v5∈Uv_5 \in Uv5​∈U , but v5v1v_5v_1v5​v1​ is an edge inside UUU . The same argument works for every odd cycle, and a graph containing an odd cycle is not bipartite.

67. Theorem 1.12. A nontrivial graph GGG is bipartite if and only if … ?

    GGG contains no odd cycles. (An odd cycle is a cycle of odd length.)

68. A nontrivial graph is bipartite if and only if it contains no odd cycles.For a connected GGG without odd cycles, how does the proof choose the partite sets?

    Fix a vertex uuu . UUU : vertices at even distance from uuu ; WWW : vertices at odd distance. It then shows that no edge joins two vertices of UUU or two of WWW . Disconnected GGG : apply this to each component.

69. Proof that a connected graph GGG with no odd cycle is bipartite: UUU = vertices at even distance from a fixed uuu , WWW = vertices at odd distance.Suppose an edge vwvwvw joins v,w∈Wv, w \in Wv,w∈W , with d(u,v)=2s+1d(u, v) = 2s + 1d(u,v)=2s+1 and d(u,w)=2t+1d(u, w) = 2t + 1d(u,w)=2t+1 . How does the proof get an odd cycle?

    Take a uuu – vvv geodesic and a uuu – www geodesic, and let xxx be their last common vertex, at distance iii from uuu . Their parts from xxx , joined by vwvwvw , form a cycle. Its length is (2s+1−i)+(2t+1−i)+1=2(s+t−i+1)+1(2s + 1 - i) + (2t + 1 - i) + 1 = 2(s + t - i + 1) + 1(2s+1−i)+(2t+1−i)+1=2(s+t−i+1)+1 , odd.

70. What is the complete bipartite graph Ks,tK_{s,t}Ks,t​ , and what is a star?

    Ks,tK_{s,t}Ks,t​ : bipartite with partite sets of sizes sss and ttt , every vertex of one adjacent to every vertex of the other. A star: K1,tK_{1,t}K1,t​ (or Ks,1K_{s,1}Ks,1​ ). K2,2K_{2,2}K2,2​ is the 4-cycle C4C_4C4​ , drawn differently.

71. What does G≅HG \cong HG≅H mean?

    GGG and HHH are the same except possibly for how they are drawn or labeled: they are isomorphic. e.g. K2,2≅C4K_{2,2} \cong C_4K2,2​≅C4​ . If the structures differ: G≇HG \not\cong HG≅H .

72. When is a graph kkk -partite, and when complete kkk -partite?

    kkk -partite: V(G)V(G)V(G) can be partitioned into kkk partite sets so that every edge joins vertices of different sets. Complete: in addition, every two vertices in different sets are adjacent. With ∣Vi∣=ni|V_i| = n_i∣Vi​∣=ni​ it is written Kn1,n2,…,nkK_{n_1, n_2, \dots, n_k}Kn1​,n2​,…,nk​​ , a complete multipartite graph. K1,1,…,1=KkK_{1, 1, \dots, 1} = K_kK1,1,…,1​=Kk​ .

73. For vertex-disjoint graphs GGG and HHH , what is the join G+HG + HG+H ?

    G∪HG \cup HG∪H together with all edges joining a vertex of GGG and a vertex of HHH . P3+K2P_3 + K_2P3​+K2​ : order 5, size 2+1+3⋅2=92 + 1 + 3 \cdot 2 = 92+1+3⋅2=9 .

74. What is the Cartesian product G×HG \times HG×H of two graphs?

    Vertices: the pairs (u,v)(u, v)(u,v) with u∈V(G)u \in V(G)u∈V(G) , v∈V(H)v \in V(H)v∈V(H) . Distinct (u,v)(u, v)(u,v) and (x,y)(x, y)(x,y) are adjacent if u=xu = xu=x and vy∈E(H)vy \in E(H)vy∈E(H) , or v=yv = yv=y and ux∈E(G)ux \in E(G)ux∈E(G) . Also written G □ HG \,\square\, HG□H . G×H≅H×GG \times H \cong H \times GG×H≅H×G .

75. How can you draw G×HG \times HG×H without labeling vertices?

    Replace each vertex xxx of GGG by a copy HxH_xHx​ of HHH ; for adjacent u,vu, vu,v in GGG , join corresponding vertices of HuH_uHu​ and HvH_vHv​ . P3×K3P_3 \times K_3P3​×K3​ : three triangles, corresponding vertices joined along P3P_3P3​ .

76. How is the nnn -cube (hypercube) QnQ_nQn​ defined recursively?

    Q1=K2\boldsymbol{Q_1 = K_2}Q1​=K2​ and Qn=Qn−1×K2Q_n = Q_{n-1} \times K_2Qn​=Qn−1​×K2​ for n≥2n \ge 2n≥2 . Q2=K2×K2=C4Q_2 = K_2 \times K_2 = C_4Q2​=K2​×K2​=C4​ , and Q3=C4×K2Q_3 = C_4 \times K_2Q3​=C4​×K2​ is the 3-cube.

77. Using nnn -bit strings (ordered nnn -tuples of 0s and 1s), how is the nnn -cube QnQ_nQn​ defined?

    Vertices: the nnn -bit strings. Two are adjacent if they differ in exactly one position. So QnQ_nQn​ has 2n2^n2n vertices.

78. What is a multigraph, and what are parallel edges?

    Multigraph: two vertices may be joined by any finite number of edges (possibly zero). Parallel edges: two or more edges joining the same two distinct vertices. Like a graph, a multigraph has a finite nonempty vertex set.

79. What is a pseudograph, and what is a loop?

    A pseudograph: like a multigraph, but edges joining a vertex to itself are allowed too. Such an edge is a loop. A loop eee joining vvv to itself is a loop at vvv ; a vertex can have any finite number of loops. M1,M2M_1, M_2M1​,M2​ : multigraphs; M3M_3M3​ : a pseudograph; M4M_4M4​ : a graph.

80. Is every graph a multigraph? Is every multigraph a pseudograph?

    Yes, and yes. A graph is a multigraph with at most one edge per pair; a multigraph is a pseudograph without loops.

81. Why can an edge of a multigraph not be taken to be a 2-element subset of the vertex set?

    Because the multiplicity of the edge must be recorded somehow. A set {u,v}\{u, v\}{u,v} appears in EEE only once.

82. S={2,3,5,8,13,21}S = \{2, 3, 5, 8, 13, 21\}S={2,3,5,8,13,21} , with i,ji, ji,j related when i+j∈Si + j \in Si+j∈S or ∣i−j∣∈S|i - j| \in S∣i−j∣∈S . Why is a multigraph a better model than a graph here?

    It can join iii and jjj by two edges when both i+j∈Si + j \in Si+j∈S and ∣i−j∣∈S|i - j| \in S∣i−j∣∈S . e.g. 3+53 + 53+5 and ∣3−5∣|3 - 5|∣3−5∣ are both in SSS . One edge still doesn't say which of the two holds.

83. What is a digraph (directed graph)?

    A finite nonempty set VVV of vertices with a set EEE of ordered pairs of distinct vertices, called directed edges or arcs. An arc (u,v)(u, v)(u,v) is drawn as a directed line or curve from uuu to vvv .

84. For an arc (u,v)(u, v)(u,v) of a digraph, uuu is adjacent to vvv , and vvv is adjacent from uuu .

    Both uuu and vvv are incident with (u,v)(u, v)(u,v) .

85. What is an oriented graph, and what is an orientation of a graph GGG ?

    Oriented graph: a digraph with at most one of (u,v)(u, v)(u,v) and (v,u)(v, u)(v,u) for every pair u,vu, vu,v . Orientation of GGG : an oriented graph obtained by giving each edge of GGG a direction. D2D_2D2​ is an oriented graph; D1D_1D1​ is not, since it has arcs in both directions between two vertices.

86. Two coins on a 2×22 \times 22×2 board. If a configuration can be changed into another by moving a coin to a free square next to it or by interchanging the coins, a graph models this. If the only change allowed is moving one coin right or up, why is a digraph needed?

    The relation is no longer symmetric: a move right or up cannot be undone by a move right or up. The resulting digraph is even an oriented graph. The digraph of the right-or-up moves on the 12 configurations.