# Tagged Questions

53 views

### Induction proof for a k-regular graph

so I've come across a weird problem. I've learned about induction before, and when it's an equation I can generally do them. However, this problem I'm having trouble with: "A k-regular graph is an ...
43 views

### IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset: \sum_{v ∈ V} deg(v) = ...
40 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)$ ...
18 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 ...
44 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 ...
79 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 ...
251 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 ...
56 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.
49 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 ...
415 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 ...
258 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 ...
89 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 ...
737 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 ...
238 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 ...
179 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$. ...
703 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 ...
241 views

### Help with induction question?

Given a graph $G = (V, E)$, the complement of G is the graph $G'$ deﬁned 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$ ...
514 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 ...
577 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 ...
242 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 ...
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 ...
167 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 ...
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 ...
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$ ...
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
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 ...