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
1answer
11 views

Prove: if the complementary graph is connected, then graph isn't necessarily unconnected.

I have such a question. There is a theorem related to graphs that says, that if a graph is disconnected then it's complementary graph is connected. But how can I prove that the inverse is not true, ...
0
votes
0answers
14 views

Symbol Identification related to set-theory and graph theory

If $A$ is a set of vertices of a graph $G$ where $A=\{V_1, V_2, V_3,V_4... V_N\}$, then what is the meaning of symbol $|A|$ ? I encountered this problem when I was reading a paper related to directed ...
2
votes
1answer
20 views

What is a graph isomorphism?

I am trying to under isomorphism in graphs, and from what I know, if graph A is isomorphic to graph B, then you could basically just rearrange the nodes in A, while keeping the edges connected the ...
0
votes
1answer
16 views

Is these Trees isomorphic or not?

Is these Trees isomorphic or not? They have same structure but they have different code. Because one of them is minimum code. Thank you for your answers in advance.
1
vote
1answer
40 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
2
votes
0answers
22 views

Quotient Groups and Covering Spaces in Painting Hanging

Consider the $1$-out-of-$n$ painting hanging problem: Given $n$ nails in a wall, how can we hang a painting such that upon removal of any nail, it falls. This has a nice interpretation as a problem in ...
0
votes
0answers
17 views
0
votes
0answers
42 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
12 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 ...
2
votes
0answers
50 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 ...
2
votes
0answers
24 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
3answers
12 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
20 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
21 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
27 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
28 views

A question about group actions on a trees [on hold]

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
21 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
28 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
36 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
26 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
22 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
33 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
17 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
427 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
44 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
22 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
60 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
29 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
85 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
18 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
20 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
33 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
24 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
24 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, ...