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 _________________________________________/ -*etr Hlinený, hl MU Brr 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 ec/g'e 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 refereed 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}| 2 3 Which one do you like more? tr Hliněný, Fl MU Brr FhMAOlO: What is a Graph Basic graph classes It is a custom to refer to some basic special graphs by a descriptive names like the following. The cycle of length n has n > 3 vertices joined in a cyclic fashion with n edges: Cr n The path of length n has n + 1 vertices joined consecutively with n edges: •-------•------•------•- 12 3 4 Detr Hlinený, Fl MU Br n n+1 F^MAOW^A/han^^Graph The complete graph on n > 1 vertices has n vertices, all pairs forming edges (i.e. (™) edges altogether): 2 Kr 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: Kr Detr Hlinený, Fl MU Br FhMAOlO: What is a Graph 1.2 Vertex degrees in a graph Definition 1.2. The degree of a vertex win a graph G, denoted by da(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 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. ü etr Hliněný, Fl MU Br FhMAOlO: 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. Since in abstract graphs, we usually have unnamed vertices, we have to sort the sequence somehow. Just to quickly ask, why the sequence 1,2,3,4, 5, 6 cannot be a degree sequence of a graph? (Is the sum even?) 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 degree sequence d\, d<2,. .., dn if, and only if there exists a simple graph on n — 1 vertices having degree sequence d\, d<2,..., dn-dn-i, dn-dn — 1,..., dn-2 — 1, dn-\ — 1. Petr Hliněný, Fl MU Brru________________________________________________MAOIO: What is a Graph r 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), and then sort again as (0,0,1,1, 2), and continue analogously with the next step to seq. (0,0,0, 0). c The last one clearly exists, and by the equivalence in Theorem 1.4, our graph exists as well, c How can we construct such a graph? See. .. • • • • • • *—~~í:^ •~^4-==»^'"řy' (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). d One more step and we get (0, 0, —1,0,0,1, 2). What does it mean? Since the degree of a graph cannot be negative, the last graph does not exist, and neither does the first one! Petr Hliněný, Fl MU E________________________________________________ Fl: MAOIO: What is a Graph 1.3 Subgraphs and Isomorphism Definition: A subgraph of a graph G is any graph Jí 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 green subgraph, 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. etr Hliněný, Fl MU Br FhMAOlO: 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 G V (G), it holds that {u, v} is an edge of G if and only if {/(«), 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? c Fact: If a bijection / is an isomorphism, then / must map the vertices of same degrees, i.e. da(v) = du(f(v)). The converse is not sufficient, however! etr Hliněný, Fl MU Br FhMAOlO: 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.) Then 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 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 —> ľ) as follows, on the picture below. The other degree-3 vertex 4 has a unique image 4'. ... The rest is then easy. .. 5 5' D etr Hlinený, Fl MU Bri Fl: MAOIO: What is a Graph r 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 D The important corollary of this claim is that the class of all graphs is partitioned into the isomorhpism 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. etr Hliněný, Fl MU Brno________________________________________________MAOIO: 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 isomorhpic to the cycle of length 3. • 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? liněný, Fl MU Bri FhMAOlO: 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, c This time, the first graph has no triangle and the second one has one! Hence they cannot be isomorhpic. D Fact: No universal and efficient way of deciding an isomorphism between two graphs is currently known (the problem is not in P). On the other hand, however, the problem is neither NP-hard, and so a general polynomial algorithm might emerge in the future. .. etr Hliněný, Fl MU Bri FhMAOlO: What is a Graph 1.4 Diredted 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 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. 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 Brne________________________________________________: MAOIO: What is a Graph On some other occasion 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 multigraphs. c Definition: A multigraph is a triple M = (V,F,e) where V P\ F 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. and etr Hliněný, Fl MU Bri FhMAOlO: What is a Graph