graph theoryinduction
I'm a little confused on the part of "induced" does this mean that from the set of vertices and set of edges that are given, that every vertex is connected to every other vertex? Or for instance, what if I have a set of vertices and a set of edges but one of the vertices is not connected to any other vertex. Would this be considered a graph? or even more specific an induced graph? Thank you
Also, can these subgraphs contain cycles?
It's a little easier:
If $G$ contains a bridge, call $H$ one of the two subgraph in which the graph is divided by the bridge.
The sum of the degrees of all the nodes in $H$ is equal to 2 times the number of edges in $H$, so it's an even number. But all the nodes in it have even degree, except for the node from which the edge departed, that has odd degree, so we have an absurdity.
Well, to start with, here are two graphs that are not isomorphic, even though they have three isomorphic vertex-deleted subgraphs:
If $G$ is the graph on the left and $H$ is the graph on the right, then:
Therefore it's not enough to have an overlap of three vertex-deleted subgraphs to conclude that $G$ and $H$ are isomorphic.
So where is the flaw in your argument? The problem that even though the subgraphs above are isomorphic, they are not compatibly isomorphic. If we give vertex $3$ in $G$ and vertex $b$ in $H$ the same name $v_1$, then $G - \{v_1\}$ isomorphic to $H - \{v_1\}$. If we give vertex $5$ in $G$ and vertex $c$ in $H$ the same name $v_2$, then $G - \{v_2\}$ is isomorphic to $H - \{v_2\}$, but in that isomorphism, the vertices we called $v_1$ aren't matched to each other!
So it doesn't make sense to say that $G$ and $H$ are isomorphic except possibly for the edge $v_1v_2$, because we don't know that we can simultaneously agree on which vertex is $v_1$ and which vertex is $v_2$.
To illustrate the subtlety of the reconstruction conjecture, here is an example in which $D(G)$ and $D(H)$ agree in all but one element:
Best Answer
A subgraph of $G$ is just any subset of $V(G)$ and any subset of $E(G)$ that is itself a graph. For example, the cycle on six vertices is a subgraph of the complete bipartite graph on eight vertices (choose three vertices from each partite set and the appropriate edges to form a cycle).
An induced subgraph is any subset $S$ of $V(G)$ with edge set $$ \{uv \mid u,v \in S \text{ and } uv \in E(G)\}. $$ In words, you choose only the vertex set for your induced subgraph and then an edge will connect two of those vertices in the induced subgraph if and only if it was present in the original graph. For example, if we choose the same six vertices as in the previous example, the induced subgraph must be the complete bipartite graph on six vertices. We have no freedom to leave out any edges as we did with subgraphs. We must take all and only those edges present between the specified vertices.