1.TheBasics生区口口Fig. 1.1.3. A graph G with subgraphs G' and G":G'is an induced subgraphof G, but G"is notand write G' =: G[v']. Thus if U C V is any set of vertices, then G[U]G[U]denotes the graph on U whose edges are precisely the edges of G withboth ends in U.If H is a subgraph of G, not necessarily induced, weabbreviate G[V(H)] to G[H]. Finally, G'CG is a spanning subgraphspanningof G if V' spans allof G, ie. if V' = V.TfTTisany set of vertices (usually of G), we write G-U forG[VU]. In other words, G-U is obtained from G by deleting all thevertices in UnV and their incident edges. If U -- [u] is a singleton, rather than G-(u). Instead of G-V(G') we simplywewriteG.write G-G'. For a subset F of [VP we write G-F := (V, E<F) and+G+F := (V, EUF); as above, G- fel and G+{el are abbreviated toedge-G-e and G+e. We call G edge-marimal with a given graph propertymaximalif G itself has the property but no graph G + ry does, for non-adjacentvertices r, y e GMore generally, when we call a graph minimal or marimal with someminimalproperty but have not specified any particular ordering, we are referringmaximalto the subgraph relation. When we speak of minimal or maximal sets ofvertices or edges, the reference is simply to set inclusionG*G'If G and G' are disjoint, we denote by G* G' the graph obtainedfrom GUG' by joining all the vertices of G to all the vertices of G'.Forcomple-example, K?+ K3 - K5. The complement G of G is the graph on Vment Gwith edge set [V?~E. The line graph L(G) of G is the graph on E inline graphwhich a,y e E are adjacent as vertices if and only if they are adjacentL(G)asedgesinGFig. 1.1.4.A graph isomorphic to its complement4 1. The Basics G
G

G Fig. 1.1.3. A graph G with subgraphs G
and G

: G
is an induced subgraph of G, but G

is not and write G =: G [ V G [ U ] ]. Thus if U ⊆ V is any set of vertices, then G [U ] denotes the graph on U whose edges are precisely the edges of G with both ends in U. If H is a subgraph of G, not necessarily induced, we spanning abbreviate G [ V (H) ] to G [ H ]. Finally, G ⊆ G is a spanning subgraph of G if V spans all of G, i.e. if V = V . − If U is any set of vertices (usually of G), we write G − U for G [ V
U ]. In other words, G−U is obtained from G by deleting all the vertices in U ∩ V and their incident edges. If U = { v } is a singleton, we write G − v rather than G − { v }. Instead of G − V (G ) we simply write G − G . For a subset F of [V ] 2 + we write G − F := (V, E
F) and G + F := (V, E ∪F); as above, G− { e } and G+{ e } are abbreviated to G − e and G + e. We call G edge-maximal with a given graph property edge￾maximal if G itself has the property but no graph G + xy does, for non-adjacent vertices x, y ∈ G. minimal More generally, when we call a graph minimal or maximal with some maximal property but have not specified any particular ordering, we are referring to the subgraph relation. When we speak of minimal or maximal sets of vertices or edges, the reference is simply to set inclusion. If G and G are disjoint, we denote by G ∗ G G ∗ G the graph obtained
from G ∪ G by joining all the vertices of G to all the vertices of G . For example, K2 ∗ K3 = K5. The complement G of G is the graph on V comple￾ment G with edge set [V ] 2
E. The line graph L(G) of G is the graph on E in which x, y ∈ E are adjacent as vertices if and only if they are adjacent line graph L(G) as edges in G. G G Fig. 1.1.4. A graph isomorphic to its complement