1
vote
2answers
37 views

graph theory: show that for k=4 hesse diagram is not a planar graph

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ For the set $A$ with $k$ elements, $k>0$ look at the diagram as a graph, it's vertices are the members of $P(A)$ ...
0
votes
0answers
17 views

Induction over DAGs

I'd like to prove a proposition true over all valid Directed Acausal Graphs. I think I can do that by starting with a graph with one node and adding either a new node and connection, or a new valid ...
0
votes
0answers
41 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
0
votes
1answer
75 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
1
vote
0answers
215 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
0
votes
2answers
54 views

Proving graph theory using induction

How would I go about proving that a graph with no cycles and n-1 edges (where n would be the number of vertices) is a tree? I am just really confused about where to start. Thanks in advance.
0
votes
1answer
48 views

Induction of graphs ????

For a graph theoretical purposes, the n-dimensional cube Q_n is a simple graph whose vertices are the 2^n points (x_1... x_n) in R^n. So that for i in [n] either x_i=1 or 0, and in which two vertices ...
2
votes
1answer
390 views

Proof Involving Connected Components of a Graph

I have the following problem: prove that every graph with $n$ vertices and $n-k$ edges has at least $k$ connected components. I have approached this proof using induction, but am having difficulty ...
1
vote
1answer
243 views

Graph Theory: Graph with bipartite subgraph has MORE than e(G)/2 edges.

Show that every loopless graph G has a bipartite subgraph with more than e(G)/2 edges. Use induction on the number of vertices. Clearly if n(G) = 2, the hypothesis holds. But I am not sure how to ...
1
vote
1answer
79 views

¿Mathematical induction GRE math?

Im studing for the GRE math subject test...i can´t get the followin problem: Using Mathematical Induction, show that it is possible to color with only two colors the regions formed by n lines in the ...
2
votes
2answers
695 views

Using induction, prove that every forest is a bipartite graph

This question is similar to Is every forest with more than one node a bipartite graph?, but requires a proof by induction. This was a past exam question. - Let P(G) be the predicate that graph ...
4
votes
1answer
224 views

In the marriage problem, if each girl knows at least $m$ boys, then there are at least $m!$ ways to arrange the marriages.

I'm finding problems concerning Hall's theorem very difficult even when they're not. (See here for example. I'm sure I wouldn't have come up with the solution in a million years even though it's ...
0
votes
1answer
175 views

Let T be a tree with sub-trees which each set has a vertex in common - hence T has a vertex in all of its sub-trees?

The question is: Let T be a tree with sub-trees $T_1,T_2,..,T_n$ such that all trees $T_i,T_j$ have a vertex in common which each set has a vertex in common - show that T has a vertex in all $T_i$. ...
0
votes
2answers
626 views

Help with graph induction question?

Given a graph $G$ with $n$ vertices, where $n$ is even, prove by induction that if every vertex has degree $n/2 + 1$, then $G$ must contain a 3-cycle. A 3-cycle is a set of 3 vertices, $a; b; c$ such ...
0
votes
1answer
231 views

Help with induction question?

Given a graph $G = (V, E)$, the complement of G is the graph $G'$ defined on the same vertex set $V$ , however, an edge is present in $G'$ provided that it is not in $G$. Prove by induction that if $G$ ...
1
vote
0answers
480 views

Proving Vizing's Theorem using Induction

So I would like to prove Vizing's theorem (let d be the maximum degree of any vertex in graph G, any graph can be edge-colored with d or d+1 colors) using induction on the edges of G...here's my ...
2
votes
3answers
520 views

Proof that a n-hypercube is n-vertex-connected

I'm new to graph theory, I'm finding it hard to get upon proofs. To prove: An n-hypercube is n-vertex connected. Approaches I thought: It holds true for n=2, so ...
0
votes
0answers
238 views

Graph problem - prove by induction

Let's have two sets - $T_1$ and $T_2$ defined as below: Def.1 : $T_1$={ T | T is a tree with at least one edge and T doesn't have vertices from 2 degree } Def.2 : Every connected graph with exactly ...
3
votes
1answer
1k views

Inductive Proof of Euler's Formula $v-e+r=2$

I'm just studying for finals here. My professor told me that there would be an inductive proof on the final, and I've never done one before. He told me a good sample problem was to prove Euler's ...
2
votes
1answer
164 views

Connected Components Graph proof

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question Prove, by induction on k, that a connected component of k nodes ...
5
votes
1answer
2k views

Induced subgraphs

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 ...
0
votes
0answers
42 views

Prove by Induction that the Hyper graph $Q_d$ has at least $2^{{2^d} - d - 2}$ spanning trees

we experimented with some pen and paper and saw that the maximal number of spanning trees can be recursively defined as: $Q(1) = 1$ $Q(2) = 4$ $Q(d) = Q(d-1) * 2^{d-1}$ for $Q_d \geqslant 1$ ...
0
votes
2answers
81 views

What is the most basic graph, and how would you use it in an induction-proof?

Can a single point be a graph? Or is it just a single edge and two vertices? How do you apply this to an induction-proof in graph-theory? thanks
0
votes
2answers
1k views

Graph theory bipartite proofs with induction

I have this question I am given in a quiz and right away I did not even do it...I absolutely suck at induction as well as any kind of proofs. This question unfortunately had both...No matter what ...
1
vote
3answers
1k views

Sufficient conditions on degrees of vertices for existence of a tree

I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me? the question: "there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are ...