$G$ is a simple graph that consists of a vertex set $V(G) = \{v_1, v_2, ..., v_n\}$ and an edge set $E(G) = \{e_1, e_2, ..., e_m\}$ where each edge is an ordered pair of vertices. The edge $\{u,v\}$ is denoted $uv$.  A walk of length $k$ is a sequence $v_0,e_1,v_1,e_2,...,e_k,v_k$ of vertices and edges such that $e_i=v_{i-1}v_i$ for all $i$. A path is a walk with no repeated vertex.    Prove:  If $G$ is a finite simple graph in which every vertex has degree at least $k$, then $G$ contains a path of length at least $k$.  I believe this has something to do with the longest path but I can't come up with a reasoning/proof that is of length of at least $k$.
121754
Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$.   Relevant definitions:  $G$ is a simple graph that consists of a vertex set $V(G) = \{v_1, v_2, ..., v_n\}$ and an edge set $E(G) = \{e_1, e_2, ..., e_m\}$ where each edge is an ordered pair of vertices. The edge $\{u,v\}$ is denoted $uv$.  A walk of length $k$ is a sequence $v_0,e_1,v_1,e_2,...,e_k,v_k$ of vertices and edges such that $e_i=v_{i-1}v_i$ for all $i$. A path is a walk with no repeated vertex.   My attempt:  Induction, for $k=1$ it's obvious.  Suppose for $k-1$ and we'll prove for $k$.  Let $G$ be a simple graph such that $\forall v \in V : d(v)\ge k$.  We can assume that there are at least $k+1$ vertices since there are $k$ neighbours to every vertex.  Let $v_0$ be some vertex, it has $k$ neighbours, we'll move to one of its neighbours say $v_1$ and remove $v_0$. So now there are $k$ vertices with a degree of at least $k-1$ and from the induction hypothesis we'll have a path of length $k$.  Is using only $k$ vertices from $n$ right? Does it keep the generality when using only all the neighbours of $v_0$?
122762
Square free graph : Graphs with minimum cycle length greater than 4.  Question : What is the maximum number of edges possible for a square free graph $G(V,E)$ given that $|V|$ = n. Is it of the order $O(n^2)$?  How does the answer change if max_degree(G) = d ($&gt;1$)?  EDIT: Out of curiosity, what is the maximum number of edges with $n$ vertices, when  we limit the  of the graph to $l$.  Thanks in advance!
4446
Let $G=(V,E)$ a graph. Prove that $G$ has no cycles if and only if $G$ has $n-m$ connected components where $n$ is the number of vertices of $G$ and $m$ is the number of edges of $G$.  The thing I did is that since $G$ has no cycles then $ \frac{m}{n} &lt;1$.  Can someone give me some hints-ideas?  Thank's in advance!
61450
Can somebody give me an example of a graph on eight vertices that has a pair of pseudosimilar vertices? Or, is it not possible? If it is not possible, please do not give me a proof, as I would like to figure out how to prove it myself.     Definition: vertices $u$ and $v$ in a graph $X$ are similar if there is an automorphism of $X$ that maps $u$ to $v$. If $u$ and $v$ are similar, then the vertex-deleted subgraphs $X-u$ and $X-v$ are isomorphic. If $X-u$ and $X-v$ are isomorphic but $u$ and $v$ are not similar, we say that they are pseudosimilar.
103810
Let $G=(V,E)$ be a graph. Suppose that for every subgraph $G'=(V',E') , G' \subset G$, we have $|E'| \le 2|V'|$. Show it's possible to direct $G$ such that any outdegree would be at most $2$.   I tried proving it by induction. I've realized that the minimum degree at any subgraph of $G$ is at most 4. I tried removing the vertex $v_0$ with the minimal degree at a certain subgraph from the original graph, claiming that the graph from the remaining vertexes can be directed as required. How can I include the vertex $v_0$ in the new directed graph such that any outdegree would still be at most 2? Thanks
66392
Show that $ G = (V, E)$ has no Hamiltonian cycle, where the vertices are $ V = \{ a, b, c, d, e, f, g \} $ and the edges are $E = \{ ab, ac, ad, bc, cd, de, dg, df, ef, fg \}$.  From my working out, the vertices $ a, b, c, d, e, f$ are odd degrees of 3 and 1. Moreover $g $ being a even vertices of 2.   There were three points that were made in my textbook to show that a graph does not contain a Hamilton circuit:   A graph with a vertex of degree one cannot have a Hamilton circuit. Moreover, if a vertex in the graph has degree two, then both edges that are incident with this vertex must be part of any Hamilton circuit. A Hamilton circuit cannot contain a smaller circuit within it.   According to the definition graph G does not have a Hamiltonian cycle because of the first definition.   However, I am confused about 2 &amp; 3 definitions and I am not sure if this graph involves them or not.
65922
I'm reading the book Graphs and Their Uses which contains the following theorem and proof:     THEOREM 2.3. A connected graph with 2k odd vertices contains a family   of k distinct trails which, together, traverse all edges of the graph   exactly once.       PROOF. Let the odd vertices in the graph be denoted by   in some order.       $a_1,a_2,\dots,a_k$ and $b_1,b_2,\dots,b_k$      When we add the $k$ edges $a_lb_l, a_2b_2 ,\dots, a_kb_k$ to the graph, all   vertices become even and there is an Eulerian trail T. When these   edges are dropped out again, T falls into k separate trails covering   the edges in the original graph.   However this doesn't seem to make sense since in the graph whose vertices have degrees 3, 1, 1, 1 there is no way to add 2 edges in such a way that the degree of all odd vertices becomes even.  What am I missing here?
76168
Does any proof exist that a simple graph with $n$ vertices such that the least vertex degree is $\geq \frac{n-1}{2}$ is a connected graph? (i.e. does such a proof have a name?)
40996
I'm trying to prove this by contradiction: if $G$ isn't complete graph, there must exist vertices $u,v \in V(G)$ for which edge $uv \notin E(G)$. Then $u$ and $v$ must have the same color in proper coloring $C$ and now I'd like to prove that by removing $u, v$ we have $\chi(G-u-v) = \chi(G) - 1$ (that would be the contradiction), but I'm not sure whether it's true.
109472
I am trying to prove the following     $d_n$ is a degree-sequence of the multigraph  $G$ (without loops) if and only if $\sum_{i=1}^{n}{d_i}$ is even and $d_1 \le\sum_{i=2}^{n}{d_i}$   I have no problems showing the first part.  By the "handshake"-lemma $\sum_{i=1}^{n}{d_i}=2e$ where $e$ is the number of edges in $G$  $$d_1 \le e $$  $$d_1\le \frac{\sum_{i=1}^{n}{d_i}}{2}$$  Hence $d_1 \le \sum_{i=2}^{n}{d_i}$  However, I don't know how to show the other part. Would appreciate some tips or hints
57844
Hello everyone interested. Here's a seemingly simple problem.  Suppose $G$ is a complete, simple graph with vertices $\{1,2,..,n\}$, $n\geq k\geq 3$.  How many cycles of length $k$ can we have on $G$?  The statement seems simple but I have trouble putting everything together.  So I say fix a vertex and start forming cycles with length k. But I get nowhere... What is the proper approach to this problem since counting is not easy? Is there a relevant theorem that I am unaware of?  Thanks for any help...
99945
I'm taking a first course in graph theory this semester and I'm working trough Graph Theory with Applications by J.A. Bonday and U.S.R. Murty. I can't find an answer to question 1.2.12(f):     (a) Show, using execise 1.2.5 that an automorphism of a simple graph $G$ can be regarded as a permutation on $V$ which preserves adjacency,and that the set of such permutations form a group $\Gamma(G)$ (the automorphism group of $G$) under the usual operation of composition.      (e) Consider the permutation group $\Lambda $ with elements (1)(2)(3), (1, 2, 3) and (1, 3, 2). Show that there is no simple graph $G$ with vertex set {1, 2, 3} such that $\Gamma(G)=\Lambda$.      (f) Find a simple graph G such that $\Gamma(G)\cong\Lambda$.
21118
I came across the formula to find the number of walks of length $n$ between two vertices by raising the adjacency matrix of their graph to the $n$-th power.   I took me quite some time to understand why it actually works. I thought it would be useful to write the proof by induction for this in my own words.    Theorem: Raising an adjacency matrix $A$ of simple graph $G$ to the $n$-th power gives the number of $n$-length walks between two vertices $v_i$, $v_j$ of $G$ in the resulting matrix.  Proof by induction: Let $P(n)$ be the predicate that the theorem is true for $n$. We let $F^{(n)}_{ij}$ be the number of $n$-length walks between vertex $v_i$ and $v_j$. $P(n)$ is then the predicate that $F^{(n)}_{ij} = A^n_{ij}$. We proceed by induction on $n$.  Base case: $P(1)$   Case 1: $F^{(1)}_{ij} = A^{(1)}_{ij} = 1$ if $\{v_i, v_j\} \in E$, so there is is a walk of length $1$ between $v_i$, $v_j$.  Case 2: $F^{(1)}_{ij} = A^{(1)}_{ij} = 0$ if $\{v_i, v_j\} \notin E$, so there can't be any walk of length $1$ between $v_i$ and $v_j$.   In both cases $F^{(1)}_{i j} = A^{(1)}_{ij}$ holds, hence $P(1)$ is true.  Inductive step: $P(n+1)$ For purpose of induction, we assume $P(n)$ is true, that is $F^{(n)}_{i j} = A^{(n)}_{ij}$ holds for $n$.  We can express a walk of length $n+1$ from $v_i$ to $v_j$ as a $n$-length walk from $v_i$ to $v_k$ and a walk of length 1 from $v_k$ to $v_j$.   That means, the number of $n+1$-length walks from $v_i$ to $v_j$ is the sum over all walks from $v_i$ to $v_k$ times the number of ways to walk in one step from $v_k$ to $v_j$. Thus:  $$F^{(n+1)}_{ij} = \sum_{k=1}^{|V|} A_{kj}F^{(n)}_{ik} = \sum_{k=1}^{|V|} A_{kj}A^{(n)}_{ik}$$  Which is the formula for the dot-product, used in matrix multplications.    Any feedback appreciated.
122373
I was asked the following question:  Let $T=\left(V,E\right)$ be a tree, and let $d$ be the maximum degree of a vertex in that tree. Assume that $d \geq 2$. Prove there an edge in the tree such that, when we remove it from $T$, we will get two trees each of which has at most $\left\lceil \dfrac{d-1}{d}\left|V\right|\right\rceil$ vertices.  I tried going by induction on $d$ the maximum degree while I set the number of vertices and it didn't worked. also tried to do induction on the number of vertices and it didn't worked too.  Thanks for the help, Yoav
109744
On the  it is mentioned that it is not a Cayley graph.    How it this proved? Honestly I don't even know how to start this. The only criteria I can think of is that all vertices must have the same degree. Also the degree being odd should imply that one generator of the group has order 2. But then how do I proceed?  Edit: As already mentioned in the comments, the link did not answer my question.
39195
I need a pair of non-isomorphic graphs with the smallest n-vertex possibility and where degree sequences are the same. Is the minimum number 2, such as a multigraph with n=2? Please help with the reasoning on this question. Thank you!
103700
I am a student in an introductory class for graph theory and this question is on our first homework assignment and I don't know where to start to prove the following:     Suppose that $n \geq 3$ and a simple graph G has $n$ vertices and at   least $(n^2 - 3n + 6)/2$ edges. Prove that G is orientable.   Thank you for your time. Any hints or help will be greatly appreciated.  EDIT: A graph g is orientable if it is the underlying graph of a strongly connected digraph. A digraph is strongly connected if for all vertices $v$ and $w$ there exists a walk $v-w$.