1 What is a Graph Graphs present a key concept of discrete mathematics. Informally, a graph consists of • vertices, sometimes called nodes ("dots"), • and edges ("arcs") between pairs of vertices. Importantly, graphs are easy to draw and understand from a picture, and easy to process by computer programs, too. c Brief outline of this lecture • What is a graph: definition of a graph and its basic terms, examples and trivial classes of graphs. • Vertex degrees, degree sequence of a graph (score). • Subgraphs and isomorphism, recognizing (non-)isomorphic graphs. • Directed graphs and multigraphs. Petr Hliněný, FI MU Brno_1_FI: MA010: What is a Graph 1.1 Denning a graph Definition 1.1. Graph (actually, a simple undirected graph) is a pair G = (V, E) where V is the vertex set and E is the edge set - a subset of pairs of vertices. Notation: An edge between vertices u and v is denoted by {u, v}, or shortly uv. The vertices joined by an edge are adjacent or neighbours. The vertex set of a (known) graph G is referred to as V(G), the edge set as E(G). c Fact: A graph is, in algebra terms, a symmetric irreflexive binary relation. c Remark: How can we describe a graph? Either by listing the vertices and edges, or with a nice picture.. . V = (1, 2, 3, 4}, E = { (1, 2}, (1, 3}, (1,4}, {3,4} 1 2 3 4 Which one do you like more? V Petr Hliněný, FI MU Brno FI:MA010: What is a Graph Basic graph classes It is a custom to refer to some basic special graphs by descriptive names such as the following. The cycle of length n has n > 3 vertices joined in a cyclic fashion with n edges: 4 3 A- 7 . . . n The path of length n has n +1 vertices joined consecutively with n edges: 1 2 3 4 ... n n+1 Petr Hlineny, FI MU Brno_3_FI: MA010: What is a Graph 5 2 1 6 The complete graph on n > 1 vertices has n vertices, all pairs forming edges (i.e. (™) edges altogether): The complete bipartite graph on m > 1 plus n > 1 vertices has m + n vertices in two parts, and the edges join all the m • n pairs coming from different parts: ,,n Petr Hliněný, Fl MU Brno FI:MA010: What is a Graph 2 3 1 m n 1.2 Vertex degrees in a graph Definition 1.2. The degree of a vertex v in a graph G, denoted by dG(v), equals the number of edges of G incident with v. An edge e is incident with a vertex v if v is one of the ends of e. c In this example, the degrees are written at the vertices. 2 >-* 2 3* 3 <- \ 3 > 3 4 < V 2 • 3 2 V ^ 5 Definition: A graph is d-regular if all its vertices have the same degree d. Notation: The maximum degree in a gr. G is denoted by A(G) and minimum by 5(G). Theorem 1.3. The sum of the degrees of all vertices of a graph is always even, equal to twice the number of edges. c Proof. When summing the degrees, every edge has two ends and hence it is counted twice. □ Petr Hliněný, Fl MU Brno FI:MA010: What is a Graph 2 The degree sequence Definition: The degree sequence (called also the score) of a graph G is the collection of degrees of the vertices of G, written in a sequence of natural numbers which is (usually) sorted as nondecreasing or nonincreasing. In abstract graphs, their vertices usually have no names, and so we have to sort their degree sequence somehow. The particular custom is not important. c Just to quickly ask, why the sequence 1, 2, 3,4, 5, 6 cannot be a degree sequence of a graph?c (Is the sum even? No. . . ) And what about the sequence 1, 2, 3,4, 5, 6, 7 ? c Theorem 1.4. Let d\ < d2 < • • • < dn be a sequence of natural numbers. There exists a simple graph on n vertices having a degree sequence if, and only if, there exists a simple graph on n — 1 vertices having the degree sequence d\, d<2,. .., dn d\, d2, . . . , dn-d„-l, dn-dn — 1, . . . , dn-2 — 1, dn-1 — 1 V Petr Hliněný, FI MU Brno FI:MA010: What is a Graph Example 1.5. Is there a simple graph with degree sequence (1,1,1, 2, 3,4) ? Using Theorem 1.4 we modify the sequence to (1, 0,0,1, 2), □ then sort again as (0,0,1,1, 2), and continue analogously with the next step, arriving at the seq. (0, 0, 0,0). □ A graph with the last degree sequence clearly exists, and so by the equivalence claim in Theorem 1.4, our graph exists as well. □ How can we construct such a graph? See. . . • •............ 1,1,1,1, 2, 3, 4, 6, 7) ? □ The first step analogously translates to (1,0,0, 0,1, 2, 3, 5), sorted as (0, 0, 0,1,1, 2, 3, 5). □ One more step and we get (0, 0, —1,0,0,1, 2). What does it mean? □ Since the degrees of a graph cannot be negative, a graph with the last sequence does not exist, and neither does the original one! □ Petr Hliněný, Fl MU Brno FhMAOlO: What is a Graph 1 1 1 _ 1.3 Subgraphs and Isomorphism Definition: A subgraph of a graph G is any graph H on a subset of vertices V(H) C V(G), such that the edges of H form a subset of the edges of G and have both ends in V(H). We write H C G as for the set inclusion. c Why, on the left hand side, the red subsets do not form a subgraph? c On the right hand side, we have got a well-formed subgraph in green colour. c Definition: An induced subgraph is a subgraph H C G such that all edges of G between pairs of vertices from V(H) are included in H. V Petr Hliněný, Fl MU Brno FhMAOlO: What is a Graph Definition 1.6. An isomorphism between graphs G and H is a bijective (one to one) mapping f : V(G) — V(H) such that, for every pair of vertices u,v G V(G), it holds that {u, v} is an edge of G if and only if {f (u), f (v)} is an edge of H. Graphs G and H are isomorphic if there exists an isomorphism between them. We write G ~ H. □ Fact: Isomorphic graphs have the same numbers of vertices and of edges. Which two of the graphs are isomorphic and why the third one is not? □ Fact: If a bijection f is an isomorphism, then f must map the vertices of same degrees, i.e. cLq(v) = dH(f (v)). The converse is not sufficient, however! V Petr Hliněný, Fl MU Brno FhMAOlO: What is a Graph We shall first compare the numbers of vertices and of edges. (Agree.) cThen we compare their degree sequences. (Again, they agree 2, 2, 2, 2, 3, 3.) cThis means we have found no easy distinction, and the graphs might (or may not!) be isomorphic. We have to start looking for all possible bijections between them. □ In this particular case, it helps to notice that the two degree-3 vertices on the left are isomorphic, and so we may choose any one of them to map it to the leftmost vertex of the second graph. □Numbering the vertices by 1, 2, 3, 4, 5, 6, we can construct our mapping (already have 1 — 1') as follows, see on the picture below. Theorem 1.8. The relation "to be isomorphic" ~ is an equivalence on the class of all graphs. Proof. We easily show that ~ is reflexive, symmetric, and transitive. □ □ The important corollary of this claim is that the class of all graphs is partitioned into the isomorphism classes. Hence when we speak about a "graph", we (usually) actually mean its whole isomorphism class. A particular presentation of the graph does not matter. Petr Hlineny, FI MU Brr FI:MA010: What is a Graph Additional graph notation Notation: Consider an arbitrary graph G. • A subgraph H C G isomorphic to a cycle is called a cycle in G. • Specially, a triangle in G is a subgraph isomorphic to the cycle of length 3. c • A subgraph H C G isomorphic to a path is called a path in G. c • A subgraph H C G isomorphic to a complete graph is called a clique in G. • A vertex subset X C V(G) such that no pair from X forms an edge of G is called an independent set X in G. c • An induced subgraph H C G isomorphic to a cycle is called an induced cycle in G. Analogously an induced path. . . What subgraphs and induced subgraphs can you find in the following graphs? 6 5 6 * 5 1 < • 4 1 < • 4 V Petr Hiineny, FI MU Brr FI:MA010: What is a Graph Example 1.9. Are the following two graphs isomorphic? • □ We start analogously to previous Example 1.7. Both these graphs have the same numbers of vertices and edges, and the same degree sequence 2, 2, 2, 2, 3, 3. However, if one tries to find an isomorphism, even exhaustively, he fails. What is going on? □ Which property of the graphs prevents us from finding an isomorphism? Since there are (especially for larger graphs) too many potential bijective mappings to try them exhaustively in practice, we shall look for some other, ad-hoc, approaches. □ This time, the first graph has no triangle and the second one has one! Hence they cannot be isomorhpic. □ □ Fact: No universal and efficient way of deciding an isomorphism between two graphs is currently known (the problem is not known in P). On the other hand, however, the problem is neither NP-hard to our knowledge, and so a general polynomial algorithm might emerge in the future. . . V Petr Hiineny, FI MU Brr FI:MA010: What is a Graph 1.4 Directed graphs and Multigraphs On some occasions, we need to express a "direction" of a graph edge. □ We then speak about directed graphs in which edges are ordered pairs of vertices (and they are drawn as arrows). Definition: A directed graph (digraph) is a pair D = (V, A) where A C V x V. Fact: Digraphs correspond to binary relations which need not be symmetric. c Notation: An edge-arrow (u,v) in a digraph D has tail in u and head in v, or it joins "from u to v". The opposite arrow (v,u) is distinct from (u, v) ! Petr Hliněný, Fl MU Brno 14 Fl:MAOlO: What is a Graph On some other occasions one may even want to speak about structures in which more than one edge exists between one pair of vertices, and the edges might have mixed types (undirected or directed, loops). We then speak about (mixed) multigraphs. c Definition: A mixed multigraph is a triple M = (V,F,e) where V n F = 0 and e : F — ("2) U V U (V x V) is an incidence mapping of (multi)edges. In the definition, • ("2) represents unoriented edges, • • • V unoriented loops, and • V x V oriented edges and loops. Petr Hiineny, FI MU Brr FI:MA010: What is a Graph