Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
0answers
27 views

What is the name of a graph structure with 'ports'?

I am wondering what the name of the following structure is. I might call it the madeup name "graph with ports" but most likely it already has a name that i am not aware of. The interesting thing to me ...
1
vote
1answer
8 views

Why can a set of edges of a bipartite graph with maximum degree d be partitioned in d matchings ?

In Wikipedia I read this: 'If there is a perfect matching, then both the matching number and the edge cover number are |V| / 2.' http://en.wikipedia.org/wiki/Matching_%28graph_theory%29 Is this the ...
1
vote
0answers
37 views

Is a “network topology'” a topological space?

Is there any connection between the computer science phrase "network topology" and the mathematical notion of a topological space (or, is there any other way to connect "network topologies" with ...
1
vote
0answers
16 views

Graphs with bounded degree: how many are there?

Can one count the number of undirected (simple) graphs on $n$ nodes with degree at most $d$? Asymptotic bounds would be helpful too.
0
votes
0answers
10 views

How many cases can draw diagonals that Applicable 2 above condition?

Imagine A $n$_regular polygon that vertex is named by $1$ to $n$. We know can draw $\frac{(n)(n+3)}{2}$ diagonals in $n$_regular polygon and also know if we want draw Maximum diagonals are not ...
0
votes
3answers
10 views

Proving if $G$ has no cycles but by adding one edge between any two vertices will create a cycle then $G$ is a tree

Prove: if $G$ has no cycles but by adding one edge between any two vertices it will create a cycle then $G$ is a tree. Below is the definition we use for a tree. I don't see any way to connect ...
1
vote
0answers
10 views

Expected size of largest connected component in a random k-out digraph?

Given a digraph with n vertices and kn edges, where each vertex has k out-neighbors randomly chosen at uniform without loops, how would I go about figuring out the expected value of the size of the ...
2
votes
1answer
20 views

Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children. I read that ...
0
votes
1answer
24 views

Let $G$ be a connected graph, then $G$ is a tree iff $G$ has no cycles

Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles. $\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles. ...
2
votes
0answers
22 views

A question about group actions on a trees

why does the following conclusion hold: Let G be a group acting on a tree $\Gamma$, H a subgroup of G with minimal subtree $\Gamma_H$ and $g\in G$ be a hyperbolic element, s.t. $\langle g\rangle\cap ...
2
votes
1answer
19 views

Given a graph on $n$ vertices find the maximum amount of edges so it can be colored with no monochromatic $K_m$

I invented a problem and I wanted to share :What is the maximum amount of edges a graph on $n$ vertices can have if it can be edge-colored with $k$ colors so that it does not have a monochromatic ...
0
votes
1answer
20 views

Confusion about Hajós construction?

I've read this article on the Hajós construction. I've tried to execute it in a small graph to see it's results, I guess it would be something like this: These are the incidency matrices of $G,H$ and ...
0
votes
1answer
27 views

Average degree of $k$-degenerate graph is $\leq 2k$

How to prove the following claim? Average degree of $k$-degenerate graph is $\leq 2k$ Definition: Graph is $k$-degenerate if for every $\,G' = (V',E') \subset G$ there exists $v \in V'$ such ...
0
votes
2answers
35 views

Graph Theory Paths

Prove that every graph $G$ with $|G| < \|G\|$ contains a P$_{4}$. (P$_{4}$ is path with length $3$, $|G|$ is the number of vertices and $\|G\|$ is the number of edges). Would induction be the ...
1
vote
1answer
23 views

Without use the theorem that state $cr(C_3 \times C_t)=t$ for $t \geq 3$, show that $2 \leq cr(C_3 \times C_3) \leq 3$

Without use the theorem that state $cr(C_3 \times C_t)=t$ for $t \geq 3$, show that $2 \leq cr(C_3 \times C_3) \leq 3$ Here is what I got This is the graph of $C_3\times C_3$. It doen't matter how ...
2
votes
1answer
20 views

Graph with fixed amount of spanning trees

"Find a graph with 8 vertices, which have exactly 27 spanning trees." How do I find such a graph, or prove one does not exist?
1
vote
0answers
28 views

Infinite connected graph such that every vertex has finite degree

Let $G=(V,E)$ be an connected graph with $|V| \geq \aleph_0$ such that $\text{deg}(v)$ is finite for all $v\in V$. Does this imply that $|V|=\aleph_0$?
0
votes
1answer
21 views

About last part of proof of Brooks' theorem in a course in combinatorics

I am reading the proof of Theorem 3.1, which is Brooks' Theorem. I cannot understand the last part of the proof, which is on p.26 (link at google book). I don't understand what is $C_{ij}'$. I ...
0
votes
0answers
9 views

Generalizing interval graphs to higher dimensions

Not every graph is an interval graph, and that makes the notion of interval graph non-trivial. I was wondering whether the following generalization of interval ...
0
votes
1answer
15 views

Use theorem 6.23 to prove that the size of every outer planar graph of order $n \geq 2$ is at most $2n-3$

Use theorem 6.23 to prove that the size of every outer planar graph of order $n \geq 2$ is at most $2n-3$ Theorem 6.23: graph $G$ is outer planar if and only if $G \vee K_1$ is planar ...
1
vote
0answers
34 views

Let there be a connected graph $H$ and $p \in \mathbb N$. When are there $p$ spanning trees so that every edge is in at least one spanning tree?

Let there be a connected graph $H$ and $p \in \mathbb N$. When are there $p$ spanning trees so that every edge is in at least one spanning tree? What is the condition that needs to be met in order ...
6
votes
2answers
424 views

Is there a planar graph that (almost) all its vertices has degree 6?

Is it true that for any $N_0\in\mathbb N$ there exists a planar graph $G=(V,E)$ on (at least) $N_0$ vertices such that at least $$|V|(1-o(1))$$ vertices has degree 6? It is easy to show that no ...
3
votes
1answer
41 views

How to find a directed graph has a $d$ length walk between each pair of vertices?

$G=(V,E)$ where $|V|=n$ The outdegree and indegree of each vertice is set to 2. It may contains self-loops. Let $d=\lceil\log_2(n)\rceil$. Start with any vertice, we hope to reach all vertices ...
1
vote
1answer
19 views

If edges of $G$ are two colored, then there is a vertex of $G$ with at most two col0or changes in the cyclic order of the edges around the vertex.

Hello there i am reading proofs from the book of Gunter M ziegler. The chapter is called Three applications of eulers formula. Know there is a proposition which i don't fully understand and help would ...
0
votes
1answer
19 views

largest independent set in a circuit of length $n$

largest independent set in a circuit of length $7$ and $n$? For $7$, I guessed it's $3$. Guidance on finding for $n$?
0
votes
0answers
7 views

$k$-ary labeled trees with distinct labels

Classical definition of $k$-ary labeled trees doesn't restrict somehow the uniqueness of tree labels inside its branches. My question: Is any special definition (name) for such trees? To clarify ...
3
votes
1answer
32 views

Every graph can be optimally colored greedily.

I was at a conference today and someone said that if the graph $G$ has chromatic number $n$ then there is a way to order the vertices so that coloring greedily gives us a coloring with $n$ colors. By ...
0
votes
1answer
34 views

Is my proof for disjoint perfect matching correct?

I want to show the following: An $n$-regularly bipartite graph has $n$ pairwise disjoint perfect matchings. My Proof: Use Induction for $n$. The $n= 1$ case is trivial. Now consider $n\to n+1$. Take ...
1
vote
1answer
39 views

Adjacency matrix and existence of triangle

Show that a graph $G$ contains a triangle (1) if and only if there exist indices $i$ and $j$ such that both the matrices $A_G$ and $A^{2}_{G}$ have the entry $(i, j)$ nonzero, where $A_{G}$ is the ...
1
vote
2answers
53 views

A problem about pigeonhole principle or graph.

Let $A=\{1,2,...,n\}$, where $\binom{n}{3}\geq n+1$. Let $A_1,A_2,...,A_{n+1}$ be distinct subsets of $A$ such that $\bigcup_{i=1}^{n+1}A_i=A$ and $n(A_i)=3$ for all $i$. How to prove or disprove that ...
0
votes
1answer
28 views

Probability of choosing a graph with Hamiltonian cycle

Given $N$ labeled points in a plane one can construct $2^{N(N-1)/2}$ graphs(Unweighted, undirected) with them. Is there any theorem that gives the probability of choosing at random from these a graph ...
1
vote
1answer
79 views

Girth and monochromatic copy of trees

Question: Prove that for every tree $T$ and every integer $g$ there exists a graph $G$ without cycles of length up to $g$ and such that every two-coloring of the edges of $G$ contains a monochromatic ...
0
votes
0answers
29 views

the number of ways a planar graph can be partitioned

i have a connected planar graph to cut into k parts and want to know how many possible solutions there are. it clearly depends on the shape of the graph since nodes all in a row cannot be partitioned ...
0
votes
1answer
34 views

Determine all connected graphs $G$ of order $n \geq 4$ such that $G \vee K_1$ is outer planar

Determine all connected graphs $G$ of order $n \geq 4$ such that $G \vee K_1$ is outer planar. My professor say the answer is $G=P_n$, but he didn't tell us why. I know that $H$ is outer planar if ...
1
vote
2answers
67 views

Graph Theory Software with simple GUI

To the best of my knowledge I cannot find, on this site, any graph theory program resources. I am looking for a program where I can draw nodes and edges and most importantly drag and drop vertices ...
1
vote
1answer
17 views

Find Planar Graph fromVertices and Faces

Could you find a 3-Regular Connected Planar Graph on 10 vertices with 8 faces? If so, explain carefully. I dont know what does regular mean. I think that 3-connected graph on 10 vertices with 8 ...
2
votes
2answers
19 views

Find Disconnect Graph with Degree Sequence

Could you find a disconnected graph with degree sequence (7,6,5,4,4,4,4,3,3,2,2)? I tried havel hakimi theorem but it is for there is graph exist or not. Solution is yes it is exist. But how can ...
1
vote
1answer
31 views

Cardinality of vertex set and edge set of an infinite connected graph

Let $G=(V,E)$ be connected such that $|V|$ is infinite. Does it follow that $|E| = |V|$? (It's easy to see that $|E|\leq |V|$.)
1
vote
1answer
33 views

Show that we can check if $G$ has a circuit in time $O(V)$.

Consider a non-directed graph $G=(V,E)$ at which it is not allowed that we have edges of the form $(v,v)$. Show that we can check if $G$ has a circuit in time $O(V)$. According to my notes, we can ...
1
vote
1answer
21 views

Prove that there is a vertex that is connected to $d$ leaves.

we know that (*): if T a tree Graph contains a vertex v with rank(v)=d then the tree includes at least $d$ leafs. Given a tree graph T(V,E) that has at least 3 vertices. for every $v\in T$ that ...
1
vote
2answers
16 views

complete DAGs extends every non-complete DAG over the same vertex set

Given a set of vertices $V$ and a directed acyclic graph $G(V,E)$, is it always possible to extend $G$ to a tournament (a complete DAG over V) ? My intuition is yes: Get the undirected graph of $G$ ...
1
vote
1answer
64 views

mantel theorem bipartite graphs, two triangles share an edge

Question: I need to prove that if a graph is s.t $|E(G)|=\frac {n^2}4 +1 $ then it contains 2 triangles that share an edge. n is even. My thoughts: Mantel's theorem gives me that I ought to have one ...
2
votes
1answer
23 views

Prove that the edge coloring number is smaller than or equal to two times the maximum degree

Let G be a graph with maximum degree ∆(G) and χ’(G) the edge coloring number. Prove that χ’(G) ≤ 2∆(G) without using Vizing's theorem. I really don't have a clue on how to tackle this problem. Can ...
1
vote
1answer
22 views

Edge coloring 3-regular Hamiltonian graph

I need to show that a 3-regular Hamiltonian graph is 3-edge-colorable. I figured I could start by constructing a Hamiltonian cycle. Every vertex in this cycle is connected with two other vertices, ...
1
vote
1answer
35 views

Prove that graph on $n$ vertices has at most $n$ cuts of size one

Can you please help me prove the following claim? Any graph on $n$ vertices has at most $n$ cuts of size one. I tried to use induction on $n$ (assume the hypothesis holds true for $k-1$ and add ...
1
vote
1answer
14 views

Exercise involving Turan's theorem

Theorem 1 $\alpha(G) \geq \frac{n^2}{2|E(G)| + n}$ where $\alpha(G)$ stands for the largest independent set of vertices in the graph $G$. Using theorem 1 prove that any graph on $n$ vertices with ...
1
vote
1answer
15 views

Prove that there is an infinite simple path in a Graph

Given a connected infinite Graph G. each vertex in G has a finite rank. Prove That : Every vertex we choose from G can be a starting vertex for an infinite simple path in G. Simple Path: a path ...
2
votes
0answers
37 views

Book or paper recommendation about “Rube Goldberg Mathematics” // e.g. Longest path problems

First: My question is not be very specific, since I lack a concrete overview, but my idea/thoughts in a nutshell: I would like to have a recommendation of a good book, paper or article about processes ...
2
votes
2answers
83 views

Prove that if complete graph K_n is edge-colored with n colors, there exists a cycle with each edge different color

If we have a complete graph $K_n$, and color its edges with $n$ colors, can we prove that there exists a cycle with each edge of a different color? (The cycle can be of any length) Thanks!
1
vote
1answer
25 views

Can we say anything about the order of the second largest eigen-value?

Suppose we have a vertex-transitive graph ($G$) with degree $n$ and the number of vertices $N$. Is it possible to say anything about the exact order of $\frac{1}{n-\lambda _2}$ in terms of $N$ and ...