Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 02 Subgraphs
Tags: examplesSwitchExample1 hasSeenConjDef

Name: Edge deletion of \(e\)
Definition: the graph \(G\), minus the edge \(e\)
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph
\(e\in E\)
Notation: \(G\setminus e\)

Name: Vertex deletion of \(v\)
Definition: the graph \(G\), minus the edge incident to \(v\), and the node \(v\)
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph
\(v\in E\)
Notation: \(G\setminus v\)

Name: A vertex-deleted subgraph
Definition: \(G\setminus v\) for some vertex \(v\)
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph

Name: An edge-deleted subgraph
Definition: \(G\setminus e\) for some edge \(e\in E\)
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph

Name: A subgraph
Definition: \((G',E')\) with \(G'\subseteq G\) and \(E'\subseteq E\)
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph
Definition2: obtained by a finite successon of vertex deletion and edge deletion (supposing finite graph)
Example: The null graph
Conjdef: A graph, equivalently

Name: \(G\) contains \(G'\)
Definition: \(G'\) is a subgraph of \(G\)
Page: 40
Chapter: 2
Section: 1
Variables: \(G=(V(G),E(G)), G'=(V(G'),V(E'))\) graphs
Notation: \(G'\subseteq G\)

Smaller0: \(G\) is vertex transitive
Greater0: are isomorphic
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) graph
\(F,F'\) subgraphs
Prefix Greater: \(F\) and \(F'\)
Smaller1: \(F,F'\) are vertex deleted subgraph

Definition: \(G-v\) for \(v\) an arbitrary vertix
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) graph
Notation: \(G-v\)
Assuming: \(G\) is vertex transitive, \(G\) not null

Definition: \(G-e\) for \(e\) an arbitrary edge
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) graph
Notation: \(G-e\)
Assuming: \(G\) is edge transitive, \(G\) not null

Name: A copy of \(F\) in \(G\)
Definition: A subgraph of \(G\) isomorphic to \(F\)
Page: 40
Chapter: 2
Section: 1
Variables: \(F,G\) graphs
Example: A \(K_3\)-subgraph is a triangle in the graph
Name2: An \(F\)-subgraph of \(G\)

Name: An embedding of \(F\) in \(G\)
Definition: An isomorphism from \(F\) to a subgraph of \(G\)
Page: 40
Chapter: 2
Section: 1
Variables: \(F,G\) graphs

Question: The number of embedding of \(F\) into \(C\)
Answer: is \(\mathrm{aut}(F)\)
Page: 40
Chapter: 2
Section: 1
Variables: \(F,G\) graphs,
\(C\) a \(F\)-subgraph of \(G\)

Name: A supergraph of \(G\)
Definition: A graph such that \(G\) is a subgraph of it
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph

Name: A proper supergraph of \(G\)
Definition: A supergraph of \(G\) distinct from \(G\)
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph

Name: A proper subgraph of \(G\)
Definition: A subgraph of \(G\) distinct from \(G\)
Page: 40
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph

Smaller0: \(\ge 2\)
Greater0: \(G\) contains a cycle
Page: 41
Chapter: 2
Section: 1
Variables: \((G,E)\) a graph
Kind: Theo
Smaller to greater: iff
Prefix Smaller: \(\delta(G)\)