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

2
votes
1answer
27 views

Understanding what a statement means

I'm trying review for the finals by reading the text but I ran into an exercise with a sentence that I can't understand. Draw the network associated with the bipartite graph. What does that ...
0
votes
0answers
92 views

number of directed acyclic graphs

Given number of vertices $k$, how many DAGs over $k$ are there? I know from here that it can be computed in a recursive manner. I am wondering whether there are other simple formulas.
1
vote
4answers
235 views

Without using Cayley’s theorem, prove that there are at most $n^{2n−2}$ labelled trees with n vertices.

I am studying for a test I have and I found a past problem which I have no idea how to go about doing.. My thoughts are. I know not to use Cayley's theorem but it says that there are $n^{n-2}$ ...
1
vote
1answer
167 views

Maximum number of edges in a simple graph?

I found that the maximum number of edges in a simple graph is equal to $$\sum\limits_{i=1}^{n-1} i$$ Where $n$ = # of vertices. For example in a simple graph with 6 vertices, there can be at most 15 ...
6
votes
1answer
167 views

Homework - Proof: Is this particular graph Hamiltonian?

I have a homework for my class to Combinatorics and Graphs which I'm not sure how to finish. The task: Let G be a simple graph on 14 vertices, with 4 vertices having degree 5 and 10 vertices having ...
1
vote
0answers
36 views

Let G=(V,E) be a K1,3- free graph

Let $G=(V,E)$ be a $K1,3\mbox{-}$ free graph. Show that there exists a maximal fixed set $S⊆V$ in relation with the inclusion with the property that for every set of vertices $T⊆V$, where $∀v ∈ V − ...
2
votes
1answer
354 views

Bitonic Shortest Paths

A sequence is bitonic if it monotonically increases and then monotonically decreases, or if by a circular shift it monotonically increases and then monotonically decreases. For example, the sequences ...
1
vote
1answer
76 views

Self-complementary graph problem

For which $n$ from $N$ is $C_{n}$ isomorphic to its complement? Blew my mind, I mean is there even one? I've been trying to find at least one, but I wasn't lucky and I can't even imagine such a ...
4
votes
2answers
404 views

Is there a graph with a single odd vertex?

This question was on the slides in my Discrete Mathematics class and I was told to draw one. I do not think it is possible. Any ideas?
4
votes
0answers
198 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
1
vote
1answer
100 views

Modified Shortest Path Problem

Consider a directed, weighted graph $G=(V, E)$ where all edge weights are positive. You have one magic star, which lets you traverse one edge of your choice for free. In other words, you may change ...
0
votes
1answer
47 views

Maximum Clique Structure and Graph Coloring

How is graph coloring related to the maximum clique structure inside a graph? Also, is graph coloring problem only studied for planar graphs?
3
votes
1answer
85 views

an interest conjecture about the length of paths in a simple graph

Let $G$ be a simple graph and let $A$ and $B$ be two different vertices of $G$. Suppose $P$ is a path between $A$ and $B$ in $G$ which satisfies the following: For every vertex $u$ of $P$, there ...
1
vote
0answers
38 views

Convert graph of triangles into edges for the sake of coloring

I have graph made of triangles, and i need to color triangles. But i already have algorithm to color edges. Is there any known algorithm to convert graph in a way to correspond edge <-> triangle? ...
16
votes
3answers
509 views

Counting the number of polygons in a figure

I often come across figures like this on the net, or as contest problems, asking to find the number of a specific type of polygon in the figure (triangles, in this case). But I've never really found ...
1
vote
0answers
18 views

Can a circuit in graph theory use a edge twice in the circuit

I need to find out a circuit in a graph that uses the edge ab, what I want to know is can the circuit use the edge ab, more than once.
1
vote
0answers
31 views

Maximization problem on a graph

Consider a graph $G(V,E)$. Let degree of each vertex be denoted to $\beta(v) < d$. Maximize the following, where $\beta(v)$ is the only variable for all vertex $v\in V$. $$ \max \sum_{(u,v)\in E} ...
0
votes
1answer
49 views

Attaching the numbers to the polygon

Suppose a regular 45-sided polygon and numbers 0,1,2,...,9. Now attach these numbers to vertices of the polygon such that for any arbitrary pair of numbers (among of 0 to 9) there exist a edge of the ...
1
vote
1answer
36 views

random graph models

What is the difference between G(n,m) and G(n,p)? In G(n,m) one picks m of the $n \choose2$ edges at random. In G(n,p) each of the $n \choose 2$ edges are present independently with probability p. ...
1
vote
1answer
93 views

Is there an efficient way for finding the chromatic number of a given graph?

On an exam, I was given the Peterson graph and asked to find the chromatic number and a vertex coloring for it. I spent quite some time playing around with different colorings and incorrectly ...
0
votes
2answers
64 views

Restriction on Graph Automorphism

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at ...
0
votes
1answer
722 views

How to find the number of vertices in a graph?

Suppose that a connected planar graph has 30 edges. If a planar representation of this graph divides the plane into 20 faces, how many vertices does this graph have? I am not sure how to get started ...
1
vote
0answers
235 views

Is D.B.West's Introduction to Graph theory a good book to start?

I am studying for International Olympiad for Informatics (IOI) and I have to have a good understanding of Graph Theory . a teacher suggested reading Introduction to Graph Theory by D.West. Is it a ...
1
vote
2answers
139 views

Graph Theory question?

Assuming that friendship is always mutual, prove that in any group of n  2 persons, there are at least 2 persons with the same number of friends in the group. How do I answer this question with a ...
1
vote
0answers
49 views

applications of product graphs

I was reading a book http://imrich.at/books/handbook-of-product-graphs-second-edition/. Under the section Preface it was written that: large networks such as the Internet graph, with several ...
1
vote
1answer
50 views

Bounds on the size of the arc set of a directed graph which is connected but not strongly connected

An exercise in Introduction to Graph Theory by Robin J. Wilson asks for a proof that, if $D$ is a simple directed graph with $n$ vertices and $m$ arcs which is connected but not strongly connected, ...
0
votes
2answers
77 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.
1
vote
1answer
52 views

Converting a graph to a biparte to find the maximal matching

Im trying to get the maximal matching via trial and error (for the matching problem) derived from the following graph: But before I do this, I know I need to convert it into a biparte graph? Ive ...
14
votes
6answers
948 views

Can an algorithm be part of a proof?

I am an undergraduate student. I have read several papers in graph theory and found something may be strange: an algorithm is part of a proof. In the paper, except the last two sentences, other ...
0
votes
1answer
106 views

Non-isomorphic labeled forests [closed]

Prove that the number of non-isomorphic labeled forests on the vertex set [n] is at least p(n) (the number of partitions of the integer n).
2
votes
0answers
81 views

How do you specify a link to a blind combinatorialist?

Regular projections of links look like graphs in the plane. So I'm wondering if it would be possible to specify a link up to isotopy with purely combinatorial data about this graph. If so, what kind ...
1
vote
2answers
115 views

Drawing a simple connected graph with certain criteria

Draw a simple graph G with 8 vertices that satisfy all of the conditions listed below: each vertex has a degree of at least 3 the graph is not regular meaning not all vertices have same degree the ...
1
vote
1answer
141 views

Adjacency Matrices

Can someone explain adjacency matrix's in simple terms? I'm not grasping the material from the text at all, and can't solve the sample solutions provided.such as k2,k3 and the reverse. I understand ...
1
vote
0answers
43 views

Family of sets. Directed acyclic graph representation.

We are given a family of sets $F=\{F_1,\ldots,F_n\}$ with each $F_i$ being a subset of a ground set $N=\{1,\ldots,n\}$. In addition, we assume for each $F_i$ that it's not the subset of another $F_j$ ...
0
votes
2answers
114 views

Euler & Hamiltonian Cycles

How would one illustrate a graph that has both an Euler cycle and a Hamiltonian cycle, but they are not the same? From what I read, the Euler cycles themselves must have included edges and vertices, ...
0
votes
1answer
33 views

Road and candidiate problem

The city has n districts and n - 1 bidirectional roads. We know that from any district there is a path along the roads to any other district. Let's enumerate all districts in some way by integers from ...
1
vote
2answers
162 views

Maximally connected planar graph

Let $G$ be a planar graph. Is it true that: (1) $G$ is a subgraph of a maximally connected planar graph. (2) If $G$ is a maximally connected planar graph with more than four vertices, then all ...
2
votes
3answers
840 views

Drawing a simple graph with a certain number of vertices

I am supposed to see if it is possible to draw a graph with 8 vertices given the degree sequence: 1,1,2,3,5,5,6,7 First I tried the handshaking lemma and it holds. So since drawing that graph is ...
4
votes
0answers
88 views

$f$-factors and fractional $f$-factors and odd cycles

For a graph $G=(V,E)$ and a nonnegative integer valued function $f$ defined on $V$, an $f$-factor of $G$ is a spanning subgraph $F\subseteq G$ such that $d_F(v)=f(v)$ for all $v\in V$. A fractional ...
1
vote
1answer
190 views

k critical graph cannot have k + 1 vertices

$k$-chromatic graph is called $k$-critical if removal of any vertex from graph makes it $k - 1$ vertex colorable. Now i have to prove that if $G$ is a $k$ critical graph then it cannot have $k+1$ ...
2
votes
1answer
216 views

Graph Colouring - Eulerian Path

I am doing some studying for a test I have in my discrete math class and I have come across this question which I am very stuck on and keep seem to find any help... If you draw a closed curve in a ...
0
votes
1answer
64 views

Vertices of a complete graph $K_6$ are painted in black and white: find a subgraph $K_3$ with vertices of the same color

Vertices of a complete graph $K_6$ are painted in black and white. Show that it contains a subgraph $K_3 \subset K_6$ with vertices of same color. I am quite newbie at discrete maths. So, any help ...
12
votes
2answers
1k views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
3
votes
3answers
160 views

Show that every graph can be embedded in $\mathbb{R}^3$

Show that every graph can be embedded in $\mathbb{R}^3$ with all edges straight. (Hint: Embed the vertices inductively, where should you not put the new vertex?) I've also received a tip ...
6
votes
1answer
288 views

How to get from Chebyshev to Ihara?

I have competing answers on my question about "Returning Paths on Cubic Graphs Without Backtracking". Assuming Chris is right the following should work. Up to one thing: The number of returning paths ...
1
vote
2answers
1k views

How many four-vertex graphs are there up to isomorphism;

Let us call graphs $G = (V,E)$ and $G' = (V', E')$ fundamentally different if they are not isomorphic. How many fundamentally different graphs are there on four vertices? This is a question on my ...
4
votes
1answer
198 views

Graph theory & Feynman integrals

I am attending a course in Graph Theory and I am interested learning something about applications of this subject to Physics, especially I would like to learn something about Feynman integrals. Could ...
7
votes
1answer
229 views

Combinatorial Interpretation of Graph Theoretical Relation Involving Chebyshev Polynomials

Given a graph $G$ and its adjacency matrix $A$. The $(i,j)$-th element of $A^r$ gives the number of ways to get from vertex $i$ to $j$ in $r$ steps (including backtracking). Now, the number of ...
0
votes
2answers
48 views

Find a graph with an adjacency matrix consisting $0$

(okay, I'm not learning math in english, so please don't be harsh with me for not using the correct terminology here, but I hope you can understand my problem. also feel free to correct me) Find a ...
2
votes
0answers
220 views

Hall's marriage theorem explanation

I stumbled upon this page in Wikipedia about Hall's marriage theorem: The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For ...