Graph Theory Here is a path with 5 vertices And here is a cycle with 5 vertices, which is typically denoted Cs g Paths and cycles are going to be particularly important, so lets define them precisely. path is a graph P=(V, E)of the form V=u1, U2,..., Un) E={1-t2,v2-t3,,tn-1-n} where n> l and vertices v1,..., Un are all distinct. Vertices u and Un are the endpoints of the path. Note that a path may consist of a single vertex, in which case both endpoints are the same. We'll often say that there is a path from u to u in a graph G; this is a shorthand for saying that a path with endpoints u and u is a subgraph of g Similarly, a cycle is a graph C=(V, E) of the form E={t-02,t2-t3,,tn-1-tn,tn-t} where n>3 and U1,..., Un are all distinct. The length of a path or cycle is the number of edges it contains. For example, a path with 5 vertices has length 4, but a cycle with 5 vertices has length 5
6 Graph Theory Here is a path with 5 vertices: And here is a cycle with 5 vertices, which is typically denoted C5: Paths and cycles are going to be particularly important, so let’s define them precisely. A path is a graph P = (V, E) of the form V = {v1, v2, . . . , v E n} = {v1 —v2, v2 —v3, . . . , vn−1 —vn} where n ≥ 1 and vertices v1, . . . , vn are all distinct. Vertices v1 and vn are the endpoints of the path. Note that a path may consist of a single vertex, in which case both endpoints are the same. We’ll often say that there is a path from u to v in a graph G; this is a shorthand for saying that a path with endpoints u and v is a subgraph of G. Similarly, a cycle is a graph C = (V, E) of the form V = {v1, v2, . . . , v E n} = {v1 —v2, v2 —v3, . . . , vn−1 —vn, vn —v1} where n ≥ 3 and v1, . . . , vn are all distinct. The length of a path or cycle is the number of edges it contains. For example, a path with 5 vertices has length 4, but a cycle with 5 vertices has length 5
Graph theor 1.6 Isomorphism Two graphs that look the same might actually be different in a formal sense. For example the two graphs below are both cycles with 4 vertices A D But one graph has vertex set (A, B, C, D) while the other has vertex set (1, 2, 3, 4) If so, then the graphs are different mathematical objects, strictly speaking. But this is a frustrating distinction; the graphs look the same! Fortunately, we can neatly capture the idea of looks the same"and use that as our main notion of equivalence between graphs Graphs G1 and G2 are isomorphic if there exists a one-to-one correspondence between vertices in G1 and vertices in G2 such that there is an edge between two vertices in G1 if and only if there is an edge between the two corresponding vertices in G2. For example, take the following correspondence between vertices in the two graphs above A corresponds to 1 B corresponds to 2 D corresponds to 4 C corresponds to 3 Now there is an edge between two vertices in the graph on the left if and only if there is an edge between the two corresponding vertices in the graph on the right. Therefore, the two graphs are isomorphic. The correspondence itself is called an isomorphism Two isomorphic graphs may be drawn to look quite different. For example, here are two different ways of drawing Cs Isomorphic graphs share a great many properties, such as the number of vertices, number of edges, and the pattern of vertex degrees. Thus, two graphs can be proved
Graph Theory 7 1.6 Isomorphism Two graphs that look the same might actually be different in a formal sense. For example, the two graphs below are both cycles with 4 vertices: A B D C 1 2 4 3 But one graph has vertex set {A, B, C, D} while the other has vertex set {1, 2, 3, 4}. If so, then the graphs are different mathematical objects, strictly speaking. But this is a frustrating distinction; the graphs look the same! Fortunately, we can neatly capture the idea of “looks the same” and use that as our main notion of equivalence between graphs. Graphs G1 and G2 are isomorphic if there exists a onetoone correspondence between vertices in G1 and vertices in G2 such that there is an edge between two vertices in G1 if and only if there is an edge between the two corresponding vertices in G2. For example, take the following correspondence between vertices in the two graphs above: A corresponds to 1 B corresponds to 2 D corresponds to 4 C corresponds to 3. Now there is an edge between two vertices in the graph on the left if and only if there is an edge between the two corresponding vertices in the graph on the right. Therefore, the two graphs are isomorphic. The correspondence itself is called an isomorphism. Two isomorphic graphs may be drawn to look quite different. For example, here are two different ways of drawing C5: Isomorphic graphs share a great many properties, such as the number of vertices, number of edges, and the pattern of vertex degrees. Thus, two graphs can be proved