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. □ 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. 1.1 Defining 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? Petr Hliněný, Fl MU Brno, 2013 2/16 Fl: 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: The path of length n has n + 1 vertices joined consecutively with n edges: n+l Petr Hliněný, Fl MU Brno, 2013 3/16 Fl: MA010: What is a Graph The complete graph on n > 1 vertices has n vertices, all pairs forming edges (i.e. (™) edges altogether): 2 K, 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: m n Petr Hliněný, Fl MU Brno, 2013 4/ 16 Fl: MA010: What is a Graph 1.2 Vertex degrees in a graph Definition 1.2. The degree of a vertex v in a graph G denoted by dc(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. □ 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 6(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. C Petr Hliněný, Fl MU Brno, 2013 5/16 Fl: MAGIO: What is a Graph 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. □ Just to quickly ask, why the sequence 1, 2, 3,4, 5, 6 cannot be a degree sequence of a graph?n (Is the sum even? No. . .) And what about the sequence 1, 2, 3,4, 5, 6, 7 ? □ Theorem 1.4. Let d\ < < • • • < dn be a sequence of natural numbers. There exists a simple graph on n vertices having a degree sequence di, d2,•••, dn if, and only if, there exists a simple graph on n — 1 vertices having the degree sequence d±, d2, ■ ■ ■, dn-dn-i, dn-dn — 1, ■ ■ ■, dn-2 — 1, dn-i — 1. Petr Hliněný, Fl MU Brno, 2013 6/16 Fl: 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 analogically with the next step, arriving at the seq. (0,0,0,0). c A graph with the last degree sequence clearly exists, and so by the equivalence claim in Theorem 1.4, our graph exists as well, c How can we construct such a graph? See. .. • • • • • • »i^^* %—^^===^^^^^^ (1,1,1,1,2,3,4,6,7) ? □ The first step analogically 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, 2013 7/16 Fl: MA010: What is a Graph 1.3 Subgraphs and Isomorphism Definition: A subgraph of a graph G is any graph if 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? □ On the right hand side, we have got a well-formed subgraph in green colour. □ 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. Petr Hliněný, Fl MU Brno, 2013 8/16 Fl: MA010: What is a Graph Definition 1.6. An isomorphism between graphs G and H is a bijective (one to one) mapping / : V(G) —>• V(H) such that, for every pair of vertices u, v e 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. c 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 / is an isomorphism, then / must map the vertices of same degrees, i.e. dc(v) — dii(f(y))- The converse is not sufficient, however! Petr Hliněný, Fl MU Brno, 2013 9/16 Fl: MA010: What is a Graph Example 1.7. Are the following two graphs isomorphic? We shall first compare the numbers of vertices and of edges. (Agree.) nThen we compare their degree sequences. (Again, they agree 2,2,2,2,3,3.) This 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, c In this particular case, it helps to notice that the two degree-3 vertices on the left are symmetric, 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. Petr Hliněný, Fl MU Brno, 2013 10/16 Fl: MA010: What is a Graph 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, c C 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 Hliněný, Fl MU Brno, 2013 11/16 Fl: 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 pat/? /n 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? 1 4 1 4 Example 1.9. Are the following two graphs isomorphic? We start analogically 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? c 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, c This time, the first graph has no triangle and the second one has one! Hence they cannot be isomorhpic. C 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.. . Petr Hliněný, Fl MU Brno, 2013 13/16 Fl: MA010: What is a Graph 1.4 Directed graphs and Multigraphs On some occasions, we need to express a "direction" of a graph edge, c We then speak about directed graphs in which edges (directed arcs) are ordered pairs of vertices (and they are drawn as arrows). Definition 1.10. Directed graph (digraph) is a pair D — (V,A) where A 0 looks as follows 6 ... n Definition: The number of arcs from u in a digraph D is called the outdegree rfp(u), and the number of those to u the indegree d]j(u). Petr Hliněný, Fl MU Brno, 2013 15/16 Fl: MA010: What is a Graph Generalizing even more... On some other occasions one may want to speak about structures in which more than one edge exist between one pair of vertices, and the edges might have mixed types (undirected or directed, loops). This leads to so called incidence model of a (multi)graph in which edges are elements on their own, along with the vertices; as oposed to our default adjacency model where only vertices are considered as core entities, c Definition: A mixed multigraph is a triple M — (V,F,e) where V fl F — 0 and e : F —>• (^) U V U (V x V) is an incidence mapping of the (multi)edges. In the definition, • V x V oriented edges and loops. • V unoriented loops, and Petr Hliněný, Fl MU Brno, 2013 16/16 Fl: MA010: What is a Graph